[Algorithm/Python] 계수 정렬(Count Sort)이란?? || Sort

📌 계수 정렬(Count Sort)

계수 정렬이란, 리스트의 원소의 개수를 세어, 개수만큼 출력하여 정렬하는 방식이다.
예를 들어 arr = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2] 를 정렬해본다고 하자면,
각 원소별로 몇 개가 존재하는지 수를 센 후, 인덱스 0을 시작으로 각 개수만큼 수를 출력해내어 정렬하는 방식이다.

계수 정렬

위의 그림처럼, 리스트의 데이터에 해당하는 인덱스의 값을 1씩 추가하여 해당 원소가 몇 개인지 수를 세어준다.
따라서, 인덱스 0부터 차례대로 세어진 수만큼 반복 출력해주면 정렬된 리스트를 확인해볼 수 있다.
 

✅[ CODE ]

arr = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]

def count(arr):
    max_value = max(arr)
    num = [0] * (max_value + 1)
    
    for i in arr:
        num[i] += 1

    for i in range(len(num)):
        for _ in range(num[i]):
            print(i, end = " ")
count(arr)

 

📌 정리

계수 정렬은 값에 따라 개수를 세어 인덱스 0을 시작으로 차례대로 출력하는 방식이다. 따라서, 모든 데이터가 양의 정수여야 한다는 조건이 만족되어야 한다. 
또한, 가장 큰 데이터와 작은 데이터의 차이만큼 리스트의 범위를 설정해줘야 한다. 따라서 두 수간의 차이가 매우 크다면, 계수정렬을 사용하는 것은 비효율적이다.
 
데이터의 개수를 N, 데이터 중 최댓값의 크기를 K라고 할 때, 계수 정렬의 시간 복잡도는 O(N + K)가 된다.
최악의 경우일 때에도 O(N + K)이므로 위에 말했던 조건에도 적합하다면 매우 효과적으로 빠르게 정렬되는 방식이다.
 
 
출처 ) 이것이 코딩테스트다 with Python