[알고리즘] Counting Sort (계수 정렬)

Counting Sort

계수 정렬은 말 그대로 데이터를 counting 하여 정렬되는 것과 마찬가지인 효과를 나타내는 정렬입니다. 앞서 보았던 정렬방식은 시간복잡도 O(N*N) 또는 O(N*logN)을 가졌습니다. 하지만 계수 정렬은 데이터를 한번씩만 접근하여  O(N)의 시간복잡도를 가질 수 있습니다. 

 

어떻게 O(N)의 시간 복잡도를 가질 수 있을까요?

 

이유는 다른 정렬들은 데이터를 비교하고 위치를 바꾸지만 계수정렬은 데이터를 순차적으로 읽으면서 해당 데이터의 개수를 counting 하여 나중에 한번에 나타내는 방식이기 때문인데요. 이와 같은 이유 때문에 언제나 사용하기보다는 특정한 범위가 있고 중복이 많을 시 정렬이 효과적이라고 볼 수 있습니다.

 

계수정렬의 작동과정을 보면

다음과 같은 상황에 효과적입니다.

 

[3, 3, 3, 2, 1, 1, 4, 2 ,4]

 

위와 같이 4이하의 숫자가 중복이 많은 경우 데이터에 한번씩 접근하여 각 숫자의 개수를 세줍니다

 

1: 2개 

2: 2개

3: 3개

4: 2개

 

그리고 count한 수를 그대로 나타내줍니다. [1, 1, 2, 2, 3, 3, 3, 4, 4]

 

따라서 데이터에 한번만 접근하고도 정렬이 된 효과를 볼 수 있습니다.

 

다음은 파이썬 코드입니다.

def counting_sort(numbers, scope):
    count = [0] * (scope + 1)
    sorted_number = []

    for i in numbers:
        count[i] += 1

    for i, v in enumerate(count):
        for _ in range(v):
            sorted_number.append(i)

    return sorted_number



if __name__ == "__main__":
    numbers = [2,2,2,1,4,3,3,3,5,6,7,8,8,8,8,10,9,6,7,7,6]
    print(counting_sort(numbers,10))

 

 

 

입출력