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

계수 정렬 (Counting Sort) 파이썬으로 구현

• 계수 정렬은 비교 정렬이 아니다.

• K가 정수일 때 (즉, K가 어떤 최대값을 가질때), 입력 요소들이 1부터 K까지의 정수라고 가정.

• 히스토그램과 같이 각 요소들이 전체 리스트에서 몇 개씩 존재하는 지를 세아려 테이블을 만든다.

• 입력된 X 아래에 몇개의 정수들이 존재하는 지에 따라 X의 위치가 결정되는 알고리즘.(예를 들어, 5보다 작은 정수 (1,2,3,4) 가 10개 존재한다면, 5가 들어갈 위치는 11번째이다.)

• 시간복잡도가 O(n)이다.

def counting_sorted(arr, K):
    c = [0] * K
    sorted_arr = [0] * len(arr)
    
    for i in arr:
        c[i] += 1
    
    for i in range(1,K):
        c[i] += c[i-1]
   
    for i in range(len(arr)):
        sorted_arr[c[arr[i]]-1] = arr[i]
        c[arr[i]] -= 1
​
    return sorted_arr
        
arr = [3, 5, 1, 2, 9, 6, 4, 7, 5]
print(counting_sorted(arr, 20))

1. 먼저, 각 요소가 몇개씩 들어있는 지를 담을 c 배열을 K 크기로 초기화 해준다.

2. 입력된 배열(arr)의 각 요소들을 세아려 c 에 기록한다.

3. c는 기록된 값을 이전 요소들의 누적 합으로 다시 할당해준다.

4. c값을 기준으로 새로운 배열에 재배치하면 완료