계수 정렬(count sort)

특정 조건이 부합할 때만 사용할 수 있지만 매우 빠른 알고리즘.
모든 범위를 담을 수 있는 크기의 리스트(배열)를 미리 선언하기 때문에 정렬할 데이터의 크기 범위가 제한되고 정수 형태로 표현할 수 있을 때만 사용 가능하다.

예제

data = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]가 주어진 경우:
최솟값은 0, 최댓값은 9이므로 0부터 9까지 인덱스를 가지는 리스트 count를 선언한다.
각 숫자의 개수를 담은 리스트 count는 0으로 초기화한다.
data의 요소를 하나씩 탐색하면서 count의 인덱스와 동일하면 1씩 증가시킨다.

구현

github link

def count_sort(array):
    count = [0] * (max(array) + 1)

    for i in range(len(array)):
        count[array[i]] += 1
    return count

if __name__ == "__main__":
    array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
    res = count_sort(array)
    for i in range(len(res)):
        for j in range(res[i]):
            print(i, end=' ')

각 숫자의 횟수를 저장하는 리스트 count는 0부터 array의 최댓값까지 저장할 수 있도록 (array+1)크기로 선언한다. 또한, 아직 개수를 세기 전이기 때문에 모든 요소를 0으로 초기화한다.
array요소를 하나씩 탐색하면서 array와 count의 인덱스가 동일하면 값을 1씩 증가시킨다.

시간 복잡도

데이터의 개수를 N, 데이터 중 최대값의 크기를 K라고 할 때 계수 정렬의 시간 복잡도는 O(N+K)이다.

O(N) : 앞에서부터 데이터를 하나씩 확인하면서 리스트에서 적절한 인덱스의 값을 1씩 증가시킨다.
O(K) : 추후에 리스트의 각 인덱스에 해당하는 값들을 확인할 떄 데이터 중 최댓값의 크기만큼 반복을 수행한다.