카운팅 정렬(counting sort) - 정렬 알고리즘, 파이썬

지금까지 배워온 정렬은 두 수의 대소를 '비교'하는 과정을 거쳐 정렬하는 comparison sort였습니다.

두 수를 반복적으로 비교해 정렬하는 comparison sort는 아무리 알고리즘을 잘 짜도 계산 복잡성이 O(nlogn)보다 큽니다.

예를 들어서 퀵 정렬(quick sort)의 계산 복잡성이 O(n^2)이고, 힙 정렬(heap sort)이 O(nlogn)이라는 점을 감안하면 이 같은 내용이 들어맞음을 확인할 수 있습니다.

 

하지만 counting sort는 non-comparison sort 기법으로 정렬에 드는 계산 복잡성을 O(n) 선까지 낮추려는 알고리즘입니다.

- counting sort

예를 들어, 다음과 같은 input array에 대해 counting sort를 수행한다면,

input array = [2, 0, 1, 4, 5, 4, 3, 2, 0, 1, 1, 0, 5, 4, 3]

첫째로, input array의 원소들의 빈도 값을 세어서 counting array에 저장해줍니다.

counting array = [3, 3, 2, 2, 3, 2]

counting array의 각 원소 값은 인덱스에 해당하는 원소가 input array에 얼마나 존재하는지 나타내줍니다.

예를 들어 counting array[0] = 3인데, 인덱스 값인 0이 원소로서 input array에 3개 들어있다는 것을 나타냅니다.

counting array[1] = 3인데 인덱스 값인 1이 원소로서 input array에 3개 들어있다는 것을 나타냅니다.

두 번째로 counting array의 각 요솟값에 직전 요솟값을 더해서 업데이트해줍니다.

counting array = [3, 6, 8, 10, 13, 15]

input array를 정렬해서 담을 output array를 만듭니다. 처음엔 비어있다는 뜻에서 모든 원소를 -1로 설정합니다. input array를 정렬해서 담을 것이므로 input array와 같은 길이로 만들어 줍시다.

output array = [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

counting array의 의미는 다음과 같습니다.

counting array[0] = 3 : 0은 output array[0]에서 output array[2]까지 3자리 차지한다.

counting array[1] = 6 : 1은 output array[3]에서 output array[5]까지 3자리 차지한다.

...

세 번째로,  역순으로 input array의 요솟값을 output array에 채워 넣습니다.

input array의 마지막 원소는 3입니다. counting array[3] = 10을 참조하면 3은 output array[9]의 자리를 차지한다는 것을 알 수 있습니다.

(끝자리부터  채워나갑니다)

output array = [-1, -1, -1, -1, -1, -1, -1, -1, -1, 3, -1, -1, -1, -1, -1]

한자리 채워 넣었으므로 counting array[3]의 값을 -1 합시다. -> counting array[3] = 9

그다음 input array의 원소는 4입니다. counting array[4] = 13을 참조하면 4는 output array[12]의 자리를 차지한다는 것을 알 수 있습니다.

output array = [-1, -1, -1, -1, -1, -1, -1, -1, -1, 3, -1, -1, 4, -1, -1]

한자리 채워 넣었으므로 counting array[4]의 값을 -1 합시다 -> 12

이렇게 채워나가는 작업을 반복하다 보면

output array = [0, 0, 0, 1, 1, 1, 2, 2, 3, 3, 4, 4, 4, 5, 5]처럼 정렬된 array를 얻을 수 있습니다.

데이터 개수가 n 일 때 input array의 빈도를 세는 계산 복잡성은 O(n)입니다. 데이터 전체를 한 번씩 훑어야 하기 때문입니다.

output array를 만들 때도 역순으로 모두 훑어야 하기 때문에 O(n)입니다. counting array를 업데이트할 때 max(요솟값 중 최댓값)

만큼 반복문이 될게 되므로 계산 복잡성 또한 O(max)가 됩니다.

결론적으로 전체적인 계산 복잡성은 O(n+max)가 됩니다. max가 충분히 작을 경우 O(n)이 되겠지만, max가 커질 경우 max가

counting sort의 계산 복잡성을 지배하게 됩니다.

코드는 다음과 같습니다.

#counting sort 구현
def counting_sort(array, max):
 
    #counting array 생성
    counting_array = [0]*(max+1)
 
    #counting array에 input array내 원소의 빈도수 담기
    for i in array:
        counting_array[i] += 1
 
    #counting array 업데이트.
    for i in range(max):
        counting_array[i+1] += counting_array[i]
 
    #output array 생성
    output_array = [-1]*len(array)
 
    #output array에 정렬하기(counting array를 참조)
    for i in array:
        output_array[counting_array[i] -1] = i
        counting_array[i] -= 1
    return output_array