계수 정렬 (Counting Sort)

계수 정렬은 이름 그대로 배열의 원소를 각각 셈으로써 정렬하는 방식입니다. 데이터의 크기가 제한되어 있고 중복된 데이터가 많을 때 효과적인데요. 배열 [2,4,0,6,1,2,8,4,9] 예를 들어 한 번 살펴보겠습니다.

EXAMPLE

계수정렬은 먼저 배열의 가장 작은 값과 큰 값이 모두 담길 수 있는 리스트를 생성합니다.

0	1	2	3	4	5	6	7	8	9
0	0	0	0	0	0	0	0	0	0

생성한 리스트에 데이터의 값과 동일한 인덱스의 값을 증가시킵니다. 

0	1	2	3	4	5	6	7	8	9
1	1	2	0	2	0	1	0	1	1

그 다음에는 리스트의 첫 번째 데이터부터 하나씩 출력합니다.

 

파이썬 코드

def counting_sort(array):
    count = [0] * (max(array) - min(array) + 1) # Count는 0으로 초기화
    for i in range(len(array)):
        ## 해당 index 값 증가
        count[array[i]] += 1
        
    ## 출력
    result = []
    for i in range(len(count)):
        for j in range(count[i]):
            result.append(i)

 

시간 복잡도

계수 정렬은 기존 정렬과 다르게 리스트를 새로 선언하므로 result 배열의 길이 n, 최대 수 k에 대해 $O(n+k)$의 공간 복잡도가 소요됩니다. 시간 복잡도 또한 배열의 길이 n과 선언한 리스트 k에 대해 for 루프를 수행하므로 $O(n+k)$가 소요됩니다. 

홍머스 정리

• 중복된 값이 많을 때는 효과적일수도
• 0과 9999 두 원소만 있는 배열에 대해서는...?

참조

• www.youtube.com/watch?v=65Ui3RNibRA&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=24