[파이썬 알고리즘] Ch 6-2. 카운팅 정렬(Counting Sort)

먼저 키값의 범위(0~9)에 해당하는 빈도수를 저장하기 위한 리스트 count를 생성한다.
입력 리스트의 모든 원소를 순회하며 각 키값에 해당하는 count 값을 증가시킨다.
count 배열을 누적합 리스트로 변환하여 각 키값이 최종 리스트에서 차지하는 위치 범위를 계산한다.
입력 리스트를 뒤에서부터 순회하면서 누적합 정보를 이용해 결과 리스트에 원소를 배치한다.

# 카운팅 정렬 함수
def counting_sort(A):
    output = [0] * len(A)               # 정렬 결과 저장용 리스트
    count = [0] * MAX_VAL               # 각 숫자 빈도 저장용 리스트

    for i in A:                         # 각 숫자별 빈도 계산
        count[i] += 1                   
    
    for i in range(1, MAX_VAL):         # 누적합 계산
        count[i] += count[i-1]          # count[i]에는 값 i가 최종 리스트에서 차지할 (마지막 위치 인덱스) + 1 이 저장됨
    
    for i in range(len(A)):             # 누적합 정보를 이용하여 결과 리스트(output)에 원소 배치
        output[count[A[i]]-1] = A[i]    # 현재 원소 A[i]가 들어갈 위치는 count[A[i]] - 1
        count[A[i]] -= 1                # 배치 후 해당 값의 count를 감소시켜 다음 위치를 가리키도록 함
    
    for i in range(len(A)):             # 정렬된 결과를 원래 리스트 A로 복사
        A[i] = output[i]



# 카운팅 정렬 테스트
MAX_VAL = 10                            # 키값의 범위(0 ~ 9)
data = [1, 4, 1, 2, 7, 5, 2]
print("non-sorted list: ", data)

counting_sort(data)
print("counting_sorted list: ", data)

# 출력 결과
non-sorted list:  [1, 4, 1, 2, 7, 5, 2]
counting_sorted list:  [1, 1, 2, 2, 4, 5, 7]