정렬 - 계수 정렬 (counting sort)

1. 카운팅 소트(counting sort)란?

🖐 각 숫자가 등장하는 횟수를 세어서 정렬!

🖐 누적합을 활용

 

2. 순서대로 생각하기

data = [0, 4, 1, 3, 1, 2, 4, 1, 5, 7, 7, 2] 일 때,

👉 각 숫자가 등장하는 횟수를 세보자

0	1	2	3	4	5	7
1	3	2	1	2	1	2

👉 누적합을 구해보자

0	1	2	3	4	5	7
1	4	6	7	9	10	12

  ✨ 각 숫자가 위치한 인덱스를 알 수 있다!

       0은 0번째, 1은 1~3번째, 2는 4~5번째 ....

👉 재배치 !

 배치하고 인덱스 줄여주고 배치하고 인덱스 줄여주고 .....

 

3. 구현하기

def counting(array,k): # 배열과 맥스값 k
    cnt_array = [0] * (k + 1)  # 초기화
    
    for num in array:
        cnt_array[num] += 1  # 빈도 수 세기
    
    for idx in range(k):  # 누적합해주자(업데이트)
        cnt_array[idx+1] += cnt_array[idx]
    
    result_array = [0] * len(array)  # 결과 배열 만들어주기(원래배열의 개수만큼)
    
    for num in array:
        result_array[cnt_array[num]-1] = num
        cnt_array[num] -= 1  #인덱스 옮겨주기
    return result_array
    
counting([0,4,1,3,1,2,4,1,5,7,7,2],1000000)
# 출력결과 : [0, 1, 1, 1, 2, 2, 3, 4, 4, 5, 7, 7]

 

3. 복잡도

👉 O(n+k)

👉 최대값에 따라 엄청난 낭비가 발생할 수도 있음