#08 계수 정렬(Counting Sort)

계수 정렬은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘

데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능.

최악의 경우에도 수행 시간O(N + K)를 보장

 

def count_sort(arr):
    counting = [0] * (max(arr)+1)
    sorted_arr = []
    
    for i in arr:
        counting[i] +=1
    for i in range(len(counting)):
        sorted_arr += [i]*counting[i]
    for i in range(len(arr)):
        arr[i] = sorted_arr[i]

 

수행 시간 비교

매우 빠른 속도

파이썬 내장 정렬은 정말 빠르다.

다음 포스팅에 python 구현되어있는 내장 sort인 tim sort에 대해서 포스팅 하겠다.