O(n) 정렬 알고리즘

계수정렬

• 모든 항목을 다 세어야함 (메모리에 배열을 할당)

리스트를 이용한 알고리즘 O(n+k)

for j in range(n):              O(k)
    L(key[A[j]]).append(A[j])   O(1)
output = []
for i in range(k):              
    output.extend(L[i])         O(|L|+1)

기수정렬

계수정렬을 서브루틴으로 사용

Sort by digit using Counting Sort O(n+b)

Total time : O(n+b)*d) = O((n+b)log_b^k)

min when b = \theta(n) = O(nlog_b^k)

if k <= n^c then O(nc)

출처

MIT 파이썬을 이용한 알고리즘