도수 정렬

도수 정렬(counting sort)은 원소의 대소 관계를 판단하지 않고 빠르게 정렬하는 알고리즘으로, 분포수 세기(distribution counting) 정렬이라고도 한다.

 

 

알고리즘 순서

 

단계 1. 배열 내 요소값들의 개수를 저장하는 카운트 배열(도수 분포표) 'f'를 생성하고 배열의 모든 원솟값을 0으로 초기화한다.  

주어진 배열 'a'를 스캔하며 원솟값이 배열 f의 인덱스와 일치하는 곳에 카운트를 올리며 도수분포표를 채운다.  

 

단계 2. 배열 f에 원소가 몇개 들어있는지 확인하기 위해 두 번째 원소부터 바로 앞의 원솟값을 더하는 과정을 통해 누적 도수 분포표를 만든다.

 

단계 3. 배열 a와 원소 수가 같은 작업용 배열 b가 필요하다. 배열 a의 원소를 맨 끝에서 맨 앞으로 스캔하면서 배열 f와 대조하여 b를 채운다. (같은 값의 원소를 중복으로 처리하지 않기 위해 대조한 이후 f배열의 원소값을 1 감소시킨다.)

 

단계 4. 정렬된 작업용 배열 b를 정렬 전 상태인 배열 a에 그대로 복사한다.

 

도수 정렬은 if 문을 사용하지 않고 for 문만 반복해서 정렬할 수 있는 알고리즘이다.

 

<code> 

def fsort(a, max):
    '''도수 정렬(배열 원솟값은 0 이상 max 이하)'''
    n = len(a)           # 정렬할 배열 a
    f = [0] * (max + 1)  # 누적 도수 분포표 배열 f
    b = [0] * n          # 작업용 배열 b
    
    for i in range(n):    # 1. 도수 분포표 만들기
        f[a[i]] += 1
    
    for i in range(1, max + 1):    # 2. 누적 도수 분포표 만들기
        f[i] += f[i - 1]
        
    for i in range(n - 1, -1, -1):    # 3. 작업용 배열 만들기
        f[a[i]] -= 1
        b[f[a[i]]] = a[i]
        
    for i in range(n):    # 4. 배열 복사하기
        a[i] = b[i]

def counting_sort(a):
    fsort(a, max(a))