계수 정렬(Counting sort)

▶계수 정렬(Counting sort)

---

정렬할 데이터의 개수를 카운트하여 정렬하는 방법이다.

O(N+k)의 시간이 걸리며, k는 정렬할 데이터의 최대 값을 의미한다.

양의 정수이면서 k값이 작은 경우 활용하기 좋은 정렬 방법이다.

정렬할 데이터가 6,4,3,1,6,5,1,4,5라면 크기 7의 배열이 필요하다.

정렬할 데이터를 처음부터 끝까지 보면서 해당 숫자의 개수를 구하고, 그 값을 누적 합으로 바꾸어 정렬에 활용한다.

좀 더 자세히 살펴보자.

정렬해야 할 데이터가 6,4,3,1,6,5,1,4,5인 경우 배열에는 아래와 같이 저장된다.

[해당 숫자의 개수]

[0]	[1]	[2]	[3]	[4]	[5]	[6]
0	2	0	1	2	2	2

이 값을 누적 합으로 바꾼다.

[숫자 개수의 누적 합]

[0]	[1]	[2]	[3]	[4]	[5]	[6]
0	2	0	3	5	7	9

이렇게 구한 누적 합은 저장될 인덱스값+1을 나타낸다. (0의 경우 무시)

즉, 1은 [0],[1]에 저장되고 3은[2], 4는[3],[4], 5는[5],[6], 6은[7],[8]에 저장된다는 의미이다.

[정렬된 데이터]

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]
1	1	3	4	4	5	5	6	6	X

이렇게 정렬이 완료된다.

정렬에 소요되는 시간이 적다는 장점이 있지만

카운팅 정렬이 가능한 상황이 제한적이며, 비교 정렬이 아니기 때문에 정렬을 위해 별도의 공간이 필요하다는 것이 단점이다.