(CS) 계수 정렬 & 기수 정렬

계수 정렬(Counting Sort)과 기수 정렬(Radix Sort)은 비교 정렬이 아닌 정렬 알고리즘으로, 특정한 상황에서 매우 효과적인 알고리즘이다.

각 정렬 알고리즘에 대해 자세하게 알아보자.

계수 정렬

계수 정렬은 범위에 해당하는 각 숫자의 빈도수를 계산하고, 빈도수의 누적값을 사용하여 데이터의 위치를 결정하여 정렬하는 알고리즘이다. 정렬할 데이터의 범위를 알고 있을 때 매우 효과적인 정렬 알고리즘이다.

비교 정렬이 아니기에 특정 상황에서 매우 빠르지만, 정렬할 데이터의 범위만큼의 추가적인 메모리가 필요하다. 

정렬 과정

1. 데이터들의 최솟값과 최댓값을 확인하여 전체 범위를 파악한다.
2. 범위에 해당하는 각 숫자의 빈도수를 세어 배열에 저장한다.
3. 각 숫자의 빈도수를 누적하여 해당 숫자의 정렬된 위치를 계산한다.
4. 누적 빈도수를 기반으로 정렬한다. => 누적 빈도수는 해당 값의 정렬된 배열에서의 마지막 위치를 나타냄을 사용

시간 복잡도

계수 정렬의 시간 복잡도를 정렬 과정을 기준으로 계산하여 보자.

빈도수를 세어 배열에 저장하는 과정은 n개의 데이터에 대한 계산 과정이므로 O(n)이다.

빈도수를 누적하는 과정은 범위 k에 대한 계산 과정이므로 O(k)이다.

따라서 계수 정렬의 시간 복잡도는 O(n+k)이다.

 

계수 정렬은 데이터의 범위(k)에 비례하는 선형 시간에 작동하기 때문에, 데이터의 크기가 아무리 커도 범위가 작으면 효율적으로 O(n)의 시간 복잡도로 동작할 수 있다. 하지만, 데이터의 범위가 예를 들어 n^2 정도로 크게 되면 메모리도 많이 사용할 뿐만 아니라 시간 복잡도가 O(n^2)이 되기에 효율적인 알고리즘이 아니다.

기수 정렬

기수 정렬은 숫자를 자릿수 단위로 비교하여 정렬하는 알고리즘이다. 가장 낮은 자릿수부터 가장 높은 자릿수까지 반복적으로 정렬 작업을 수행하여 전체적으로 정렬을 완성한다.

비교하여 정렬하는 것이 아니기에 일반적인 비교 정렬 알고리즘보다 빠르지만, 기수 테이블의 크기만큼의 메모리가 더 필요하다. 예를 들어 10진수라면 0~9까지의 각 데이터를 담을 추가적인 메모리가 필요한 것이다.

정렬 과정

1. Queue(버킷)을 0번부터 9번까지의 10개를 둔다. (10진수이므로)
2. 주어진 수들에서 가장 낮은 자릿수와 동일한 버킷에 값을 둔다.
3. 0번 버킷부터 차례대로 값을 가져온다.
4. 다음 자릿수로 옮겨 2번 과정부터 반복하여 마지막 자리까지 진행한다.

위의 그림과 같이 기수 정렬로 주어진 수들을 간단하게 정렬할 수 있다.

시간 복잡도

기수 정렬의 시간 복잡도를 계산하여 보자. 자릿수가 d인 n개의 데이터를 정렬한다고 가정하겠다.

기수 정렬은 각 자릿수마다 정렬을 수행하는 것이므로 자릿수 하나를 정렬하는 시간에 전체 자릿수를 곱하면 시간 복잡도를 알 수 있다.

이를 계산해 보면 n개의 데이터에 대해 d번의 정렬을 수행하는 것이므로 O(d * n)라고 볼 수 있다.

 

보통 비교 정렬 알고리즘의 시간 복잡도가 O(nlongn)인걸 고려하였을 때 만약 d가 logn보다 작으면 비교 정렬보다 기수 정렬이 더 빠를 것이며, 오히려 더 큰 경우엔 비교 정렬에 비해 시간 복잡도가 더 커질 수도 있다. 그렇기에 자릿수의 크기와 전체 데이터 수를 고려하여 적절한 정렬 알고리즘을 선택하는 것이 필요하다.

참고 링크

Counting Sort Algorithm

Radix Sort | Brilliant Math & Science Wiki