계수 정렬

계수 정렬이란?

카운팅 정렬 (Counting Sort)이라고 부르기도 하는 계수정렬은 O(n)의 시간복잡도를 가지는 정렬이다.

최댓값과 입력 배열의 원소 값 개수를 누적합으로 구성한 배열로 정렬을 수행한다.

 

계수 정렬의 특징

주어진 데이터의 범위가 작은 경우 빠른 속도를 갖는 정렬 알고리즘이다.

0과 양수 범위의 데이터들만 정렬할 수 있다.

 

데이터의 범위가 커지게 되면 소요되는 시간이 커지게 되고, 메모리가 낭비되는 문제가 발생한다.

또한 음수 범위의 데이터들은 정렬할 수 없다는 단점을 가진다.

 

계수 정렬의 과정

1. 정렬되지 않은 수들을 count 배열에 몇 번씩 등장하는지 적어둔다.
2. count 배열을 앞에서부터 순회하며 등장 횟수를 누적합으로 변경한다.
3. 기존의 배열의 뒤에서부터 누적합 결과를 인덱스로 사용하여 새로운 배열에 정렬을 한다.

계수 정렬 예시

● 기존의 배열

3

1

5

6

1

3

 

● count 배열

0	1	2	3	4	5	6
0	2	0	2	0	1	1

 

● 누적합으로 변경

0	1	2	3	4	5	6
0	2	2	4	4	5	6

 

1. Phase 1

기존 배열의 마지막 데이터인 3부터 정렬해 보자.

인덱스 3의 누적합이 4이므로 3은 정렬된 배열의 4번째 칸에 들어가면 된다.

그 후 누적합 배열의 인덱스 3의 값을 1 줄인다.

 

3

 

0	1	2	3	4	5	6
0	2	2	3	4	5	6

 

2. Phase 2

다음으로 정렬해줘야 할 데이터는 1이다.

인덱스 1의 누적합이 2이므로 1은 정렬된 배열의 2번째 칸에 들어가면 된다.

그 후 누적합 배열의 인덱스 1의 값을 1 줄인다.

 

1

3

 

0	1	2	3	4	5	6
0	1	2	3	4	5	6

 

3. Phase 3

다음으로 정렬해줘야 할 데이터는 6이다.

인덱스 6의 누적합이 6이므로 6은 정렬된 배열의 6번째 칸에 들어가면 된다.

그 후 누적합 배열의 인덱스 6의 값을 1 줄인다.

 

1

3

6

 

0	1	2	3	4	5	6
0	1	2	3	4	5	5

 

4. Phase 4

다음으로 정렬해줘야 할 데이터는 5이다.

인덱스 5의 누적합이 5이므로 5는 정렬된 배열의 5번째 칸에 들어가면 된다.

그 후 누적합 배열의 인덱스 5의 값을 1 줄인다.

 

1

3

5

6

 

0	1	2	3	4	5	6
0	1	2	3	4	4	5

 

5. Phase 5

다음으로 정렬해줘야 할 데이터는 1이다.

인덱스 1의 누적합이 1이므로 1은 정렬된 배열의 1번째 칸에 들어가면 된다.

그 후 누적합 배열의 인덱스 1의 값을 1 줄인다.

 

1

1

3

5

6

 

0	1	2	3	4	5	6
0	0	2	3	4	5	5

 

6. Phase 6

마지막으로 정렬해줘야 할 데이터는 3이다.

인덱스 3의 누적합이 3이므로 3은 정렬된 배열의 3번째 칸에 들어가면 된다.

그 후 누적합 배열의 인덱스 3의 값을 1 줄인다.

 

1

1

3

3

5

6

 

0	1	2	3	4	5	6
0	0	2	2	4	5	5

 

위와 같은 과정을 거쳐 정렬이 완료된다.

 

계수 정렬의 시간 복잡도

n개의 데이터들을 순회하면서 count 배열을 만들고, 이를 다시 순회하며 누적합으로 값을 변경해 주었다.

또한 n개의 데이터의 값과 누적합 배열을 참조하여 새로운 n개의 데이터를 가지는 배열을 만들어주었으므로 계수 정렬의 시간 복잡도는 O(n)이다.