계수 정렬(Counting Sort)

계수 정렬이란?

정렬되어 있지 않은 Array List를 정렬하기 위해 그 값이 몇개 있는지 세는 작업을 하고, 선형 시간에 정렬하는 알고리즘이다.

계수 정렬 알고리즘은 다음과 같다.

1. 정렬 되어 있지 않은 배열을 받아들인다.

2. 각 값마다 몇개가 있는지 새로운 배열에 적는다.

(즉, 아래 2번의 배열은 1이 2개, 2가 3개, 3이 2개, ... ,7이 1개)

3. 2번 배열을 누적합 하여 7번배열까지 더한다.

(0 + 2 = 2, 2 + 3 = 5 , ..., 9 + 1 = 10)

4. 3번 배열을 이용하여 4번 배열에 각 번호에 맞게 값을 하나씩 주고, -1씩 해준다.

이 과정에 대해서는 아래에 계수 정렬 연습 스크립트를 넣어두겠다.

시간복잡도는 O(n)이다.

 - n개의 숫자를 정렬하는데 걸리는 시간은 O(n)

 - 각 숫자가 나온 횟수를 세는데 O(n)

 - 다시 숫자를 정렬된 리스트에 채워넣는데 O(n)

화면이 잘려 보인다면

https://www.cs.usfca.edu/~galles/visualization/CountingSort.html

사이트를 참조하면 된다.