계수 정렬 (Counting sort)

참조 :

debuglog.tistory.com/68

Python으로 알고리즘 공부 03. 계수 정렬 (Counting Sort)

m.blog.naver.com/PostView.nhn?blogId=dnpc7848&logNo=221439395086&proxyReferer=https:%2F%2Fwww.google.com%2F

---

■ 계수정렬

• 정의 :
  중복된 값이 많이 분포되어 있는  자연수의 배열 정렬시 효과적
  - 일반적으로 양의 정수(자연수)에 대해서만 정렬 가능
  - 어떤 정수 'K'에 대해 정렬 대상 array 가 "1 ~ K" 까지일 때 사용 (정렬 대상 arr 안의 최대 자연수가 K)
• 복잡도 :
  O(N)
  
  
• 예시 :

def counting_sorted(arr):
    K = max(arr) # 최대 자연수, 이 값을 입력값으로 받을 수도 있음
    assert min(arr) > 0 # 배열이 자연수 집합 조건
    
    C = [0] * (K + 1)
    sorted_arr = []
    for num in arr:
        C[num] += 1
        
    for n, counted in enumerate(C):
        if n >= 1:
            sorted_arr.extend([n]*counted)

    return sorted_arr
        
arr = [3, 5, 1, 2, 9, 6, 4, 7, 5]
print(counting_sorted(arr))

>>> [1, 2, 3, 4, 5, 5, 6, 7, 9]