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

참고 도서: 최영규, ⌜파이썬 알고리즘⌟ 생능츨판, 2021

입력의 종류에 따라서 리스트의 각 항목들을 단순히 카운트(count)하는 방법으로 정렬할 수 있는데
이러한 정렬 기법을 카운팅 정렬(Counting sort)이라고 한다.

< 카운팅 정렬 기본 전략 >

• 리스트를 한 번 스캔하면서 각 항목이 리스트에 몇 번 나타났는지 빈도수를 계산한다.
• 빈도수가 구해지면 가장 작은 항목부터 순서대로 빈도수 만큼 나열한다.

1. 카운팅 정렬을 적용하기 좋은 입력

• 키(value)가 가질 수 있는 값이 일정한 개수로 제한되는 경우
• $e.g. \ $ ALGORITHM → AGHILMORT (ASCII code는 모두 0 ~ 255사이의 값을 갖는다.)
  
  
  
  
  

2. 카운팅 정렬 알고리즘

$e.g.$
키값은 0부터 9까지라고 가정하고, 입력 리스트 [1, 4, 1, 2, 7, 5, 2]를 정렬 하려고 한다.

$sol.$

먼저 키값의 범위(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]

3. 복잡도 분석

3-1. 시간 복잡도

카운팅 정렬 알고리즘의 모든 루프는 단일 루프로 이루어져 있으므로 시간 복잡도는 다음과 같다.

$if. \ $ 입력의 크기가 $n$이고, 숫자의 범위가 $k$가지(0 ~ $k$-1)라면?

• $O(k+n)$
• $k$가 영향을 미치지 않을 만큼의 작은 수라면 $O(n)$이라고 봐도 무방하다.
  
  

3-2 공간 복잡도

해당 알고리즘은 입력 리스트에 추가적으로 $O(k+n)$의 메모리 공간을 필요로 한다.

$if. \ $ $k$가 매우 크다면?

• 매우 많은 공간이 추가로 필요하기 때문에 적용하지 않는 것이 좋다.