도수 정렬

도수 정렬

 

원소의 대소 관계를 판단하지 않고 빠르게 정렬하는 알고리즘으로, 다음과 같은 과정을 통해 if 문을 사용하지 않고 for 문만 반복해서 정렬할 수 있습니다.

 

비교/교환 작업이 필요 없어 매우 빠르지만, 데이터의 최솟값과 최댓값을 미리 알고 있는 경우에만 적용할 수 있습니다.

 

① 도수 분포표 만들기

② 누적 도수 분포표 만들기

③ 작업용 배열 만들기

④ 배열 복사

 

도수 분포표 만들기

 

각 학생의 점수를 나타내는 배열 a가 있습니다. [5, 7, 0, 2, 4, 10, 3, 1, 3] (e.g. a[0]은 5점)

이때 0~10점을 나타내기 위한 원소 수 11개인 배열 f를 만듭니다. 그리고 각각 그 값을 넣어줍니다.

for i in range(n):
    f[a[i]] += 1

 

도수 분포표 배열 [1, 1, 1, 2, 1, 1, 0, 1, 0, 0, 1]

 

누적 도수 분포표 만들기

 

'0점부터 n점까지 학생이 몇 명 있는지'를 누적된 값을 나타내는 누적 도수 분포표를 만듭니다.

이는 배열 f의 두 번째 원소부터 바로 앞의 원소를 더하는 과정을 마지막 원소까지 수행합니다.

for i in range(1, max + 1):
    f[i] += f[i-1]

 

누적 도수 분포표 배열 [1, 2, 3, 5, 6, 7, 7, 8, 8, 8, 9]

 

작업용 배열 만들기

 

이제 배열 a의 각 원솟값과 누적 도수 분포표 배열 f를 대조하여 정렬을 완료한 배열을 만드는 작업입니다. 이 작업에는 배열 a와 원소 수가 같은 작업용 배열 b가 필요합니다. 배열 a의 원소를 맨 끝에서 맨 앞으로 스캔하면서 배열 f와 대조합니다.(맨 앞부터 스캔하면 안정적이지 않습니다)

 

예를 들어 a[8]의 값은 3입니다. 이때 f[3]은 5이므로, 0~3점 사이에 학생이 5명 있다는 의미입니다. 이때 f[3]의 값을 5에서 4로 1만큼 감소시키고, b[4]에 a[8]인 3을 대입합니다.

 

왜 -1을 해야할까? a[6]의 값도 3입니다. 앞서 a[8]의 값도 3이므로 b[4]에 3을 넣었습니다. 그러므로 f[3]의 값을 4에서 3으로 1만큼 감소시키고, b[3]에 a[6]인 3을 대입합니다. 즉, 같은 값의 원소를 중복으로 처리하기 위함입니다.

for i in range(n-1, -1, -1):
    f[a[i]] -= 1
    b[f[a[i]]] = a[i]

 

 

배열 복사하기

 

정렬은 완료되었지만 정렬한 결과가 저장되는 것은 작업용 배열 b이므로 배열 a는 정렬하기 이전 상태입니다. 다음과 같은 for 문을 사용하여 배열 b의 모든 원소를 배열 a에 그대로 복사합니다.

for i in range(n):
    a[i] = b[i]

 

최종 코드

 

def fsort(a: MutableSequence, max: int) -> None:
    """도수 정렬(배열 원솟값은 0 이상 max 이하)"""
    n = len(a)
    f = [0] * (max + 1)
    b = [0] * n

    for i in range(n):              f[a[i]] += 1
    for i in range(1, max + 1):     f[i] += f[i-1]
    for i in range(n-1, -1, -1):    f[a[i]]  -= 1; b[f[a[i]]] = a[i]
    for i in range(n):              a[i] = b[i]