[알고리즘] 계수정렬

7. 계수정렬

counting sort, 범위가 명확히 정해진 data들에 대해 크기(size 혹은 개수)를 기준으로 개수를 세고 이를 정렬하는 방법을 말한다.

퀵정렬, 병합정렬보다도 시간복잡도 관점에서 가장 강력한(O(N)) 정렬방법이지만, 반드시 특정한 범위(좁은 영역) 내에 data가 분포해있어야 사용가능한 정렬이다.

7-1. 정렬방법

[1 1 1 3 5 5 3 3 2 1 2 3 4 4 5]와 같은 배열이 있을때, 계수정렬을 이용하면 빠른 차순정렬이 가능하다.

크기(1의 개수 x, 2의 개수 y, 3의 개수 z, ...)를 센 후에 그대로 정렬을 진행하므로, 데이터 위치를 따로 바꿀 필요없이 바로 정렬하는 관점에서 매우 효율적이고 빠른 정렬방법이다.

7-2. 파이썬 코드

data들의 숫자(크기, 개수)를 먼저 센 후, 개수에 따라 그대로 정렬한다.

array = [1, 3, 2, 4, 3, 2, 5, 3, 1, 2,
         3, 4, 4, 3, 5, 1, 2, 3, 5, 2,
         3, 1, 4, 3, 5, 1, 2, 1, 1, 1]
count = 5 #범위가 정해져 있을떼

countSort = [0, 0, 0, 0, 0]
result = []

for j in range(0, len(array)):
        countSort[array[j]-1] = countSort[array[j]-1] + 1

print(countSort)

for i in range(0, count):
    print(i)
    if countSort[i] != 0:
        for j in range(countSort[i]):
            result.append(i + 1)


print(result)