계수정렬 (Counting Sort)

계수는 수를 계산하다는 의미입니다. 계수 정렬에서는 정렬하고자 하는 데이터 안에 동일한 원소가 몇 번 들어 있는지를 계산하여 그 결과를 별도의 배열 또는 리스트에 저장하여 정렬에 사용합니다. hash table과 비슷한 아이디어라고 생각됩니다.

 

[아이디어]

1. 정렬할 데이터를 M이라고 할 때, M에서 가장 큰 값을 V라 합니다. 0 ~ V(총 V+1 개) 사이의 데이터 개수를 저장할 수 있는 배열 또는 리스트 N을 생성하고 N의 각 원소들을 0으로 초기화합니다.
   • 예를 들어 M = [7, 5, 2, 3, 7, 1]이라 할 때 N = [0, 0, 0, 0, 0, 0, 0]이 됩니다.
2. M을 선형으로 탐색하면서 M의 값에 해당하는 N의 인덱스 원소의 값에 1씩 더해갑니다.
   • M의 모든 원소들의 값을 살펴보면 1, 2, 3, 5는 각각 1회씩 7은 2회 포함되어 있습니다.
   • 따라서 N[1], N[2], N[3], N[5]는 모두 1이 되고 N[7]은 2가 되어 N = [0, 1, 1, 1, 0, 1, 0, 2]의 형태가 됩니다.
3. N을 선형으로 탐색하면서 각 원소의 데이터만큼 데이터의 인덱스를 출력해 줍니다.
   • 위의 예에서 N = [0, 1, 1, 1, 0, 1, 0, 2] 이므로, 1, 2, 3, 4, 7, 7의 결과가 출력되게 됩니다.

 

[특징]

1. 정렬할 데이터의 개수를 N, 정렬할 데이터의 최댓값을 K라 했을 때 계수 정렬의 시간복잡도와 공간복잡도는 O(N + K)가 됩니다.
2. 데이터의 범위가 좁게 한정되어 있을 때 효율이 극대화됩니다.

 

[구현]

array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
print('not-sorted:', ', '.join(map(str, array)))
count = [0] * (max(array) + 1)  # 0을 포함한 양의 정수 범위 안에서만 정렬이 가능
for n in range(len(array)):
    count[array[n]] += 1
result = []
for i in range(len(count)):
    for _ in range(count[i]):
        result += [i]
print('sorted:    ', ', '.join(map(str, result)))