[자료구조 및 알고리즘] 계수 정렬(Counting sort)

 

정렬 방법 중 가장 빠른 것은 O(nlogn)의 시간복잡도를 갖는다고 생각할 수 있다. 하지만 이보다 빠른 O(n)의 시간복잡도를 갖는 정렬방법도 있다. 바로 계수 정렬 다른 말로, 카운팅 정렬이다. 하지만 이러한 계수 정렬은 약간 제한된 조건 하에서 사용가능하다.

1 5 2 3 2 5 1 4 4 2 5 1

위와 같은 수가 나열되어있고 이를 정렬해보자. 그런데 자세히 보면, 위에서 등장하는 수의 범위가 1~5까지라는 것을 알 수 있다. 이처럼 수의 범위가 정해져 있는 경우 계수 정렬을 사용하면 효율적으로 정렬할 수 있다.

카운팅 정렬이란 말 그대로 수가 등장하는 횟수를 카운트 하는 것이다. 카운팅이 다 끝나면 크기 순서대로, 해당 수가 등장하는 횟수만큼 print해주면 된다. 위의 경우, 등장하는 수를 카운팅하여 arr[i]가 i가 등장하는 수를 담고 있는 리스트를 만들어보면 아래와 같다.

인덱스	0	1	2	3	4	5
값	0	3	3	1	2	3

 

위와 같이 카운팅이 완료되면 인덱스 순서대로 따라가며 갯수만큼 print해주면 정렬이 완료된다. 0은 0개를, 1은 3개를, 2는 3개를, 3은 1개를, 4는 2개를, 5는 3개를 출력하면 된다.

정렬된 순서 : 1 1 1 2 2 2 3 4 4 5 5 5

계수 정렬의 또 다른 장점은 다른 정렬들처럼 swap을 사용하지 않는다는 것이다. 또한 데이터를 한 번씩만 접근한다는 점에서(O(n)) 효율적이다.