도수 정렬은 원소의 대소 관계를 판단하지 않고 빠르게 정렬하는 알고리즘으로, 분포수 세기 정렬이라고도 한다.
도수 정렬 알아보기
지금까지 학습한 정렬 알고리즘에서는 두 원소의 키값을 비교하여 정렬했다. 하지만 도수 정렬은 원소를 비교할 필요가 없다는 특징이 있다. 아래 그림은 10점 만점 테스트에서 학생 9명의 점수를 도수 정렬하는 알고리즘을 나타낸 것이다.
정렬할 배열은 a, 원소 수는 n, 점수의 최댓값은 max이다.
1단계: 도수 분포표 만들기
먼저 아래 그림처럼 배열 a에 있는 학생들의 점수를 바탕으로 '각 점수에 해당하는 학생이 몇 명인가'를 나타내는 도수 분포표를 만들어야 한다. 도수 분포표를 저장하는 곳은 원소 수가 11개인 배열 f이다.(0~10점을 나타내기 위해 원소는 총 11개이다)
먼저 배열 f의 모든 원솟값을 0으로 초기화한다.(0) 그런 다음 배열 a의 맨 앞부터 스캔하면서 도수 분포표를 만든다. 처음에 주목한 a[0]은 5점이므로 f[5]에 1(1명 추가)을 증가시킨다.(1) 그 다음 a[1]은 7점이므로 f[7]에 1을 증가시킨다.(2) 이 작업을 배열 a의 맨 끝인 a[n - 1]까지 반복하면 배열 f의 도수 분포표가 완성된다.
2단계: 누적 도수 분포표 만들기
다음으로 '0점부터 n점까지 학생이 몇 명 있는지'를 누적된 값을 나타내는 누적 도수 분포표를 만든다. 아래 그림은 배열 f의 두 번째 원소부터 바로 앞의 원솟값을 더하는 과정을 나타낸다. 가장 아래에 있는 배열 f는 완성된 누적 도수 분포표이다.
예를 들어 f[4]의 값인 6은 0~4점을 받은 학생의 누계가 6명이고, f[10]의 값인 9는 0~10점을 받은 학생의 누계가 9명이라는 것을 의미한다.
3단계: 작업용 배열 만들기
앞의 단계에서 각 점수를 받은 학생이 몇 번째에 위치하는지 알 수 있으므로 이 시점에서 정렬은 거의 마쳤다고 할 수 있다.
남은 작업은 배열 a의 각 원솟값과 누적 도수 분포표 f를 대조하여 정렬을 완료한 배열을 만드는 것이다. 이 작업에는 배열 a와 원소 수가 같은 작업용 배열 b가 필요하다. 배열 a의 원소를 맨 끝에서 맨 앞으로 스캔하면서 배열 f와 대조한다.
아래 그림은 작업용 배열을 만드는 과정을 보여준다. 이 그림과 작업용 배열 b를 만드는 아래의 for 문을 같이 비교하면서 살펴보자.
위 그림에서 배열 a의 맨 끝 원소인 a[8]의 값은 3이다. 누적 도수를 나타내는 배열 f[3]의 값이 5이므로 0~3점 사이에 학생이 5명 있다는 의미이다. 그러므로 작업용 배열 b[4]에 3을 저장한다.(2) 저장을 하기 전에 f[a[i]] -= 1을 수행한다.(1) 즉, f[3]의 값을 5에서 4로 1만큼 감소시켜 만든다.
배열 b의 다섯 번째 원소 인덱스는 5가 아닌 4라는 점을 주의해야 한다. 배열 b에 저장하기 전 (1)에 의해 f[a[i]]를 1 감소시킨다. 즉, f[3]의 값이 5에서 4가 된다.
아래 그림에서 배열 a는 맨 끝에서 맨 앞을 향해 스캔하므로 a[8]의 하나 앞 원소인 a[7]의 값 1에 주목한다. 누적 도수를 나타내는 배열 f[1]의 값 2는 0~1점 사이에 학생이 2명 있다는 것을 보여준다. 그러므로 작업용 배열 b[1]에 1을 저장한다.(위 그림의 2번 코드)
배열 b의 두 번째 원소 인덱스는 1이다. 배열 b에 저장하기 전에 f[1]의 값을 2에서 1로 1 만큼 감소시킨다.(위 그림의 1번 코드)
아래 그림에서 다음에 주목하는 a[6]의 값은 3이다. 3점인 학생은 이전 그림에서처럼 이미 저장했으므로 두 번째 하는 것이다. 이전 그림에서는 a[8]을 작업용 배열 b에 저장할 때 f[3]의 값을 1 감소시켜 5에서 4로 만들었다. 작업용 배열의 네 번째 원소인 b[3]에 저장한다. 이렇게 미리 값을 감소시켰기 때문에 중복되는 값을 3인 배열 b[3]에 저장할 수 있다. 작업용 배열 b에 값을 저장할 때 참조한 배열 f의 원솟값을 1 감소시킨 이유는 같은 값의 원소를 중복으로 처리하지 않기 위한 것이다.
정렬하기 전 배열의 맨 끝 쪽 a[8]의 값인 3은 b[4]에 저장되고, 맨 앞 쪽 a[6]의 값인 3은 b[3]에 저장되었다.
이 작업을 a[0]까지 수행하면 배열 a의 모든 원소가 작업용 배열 b의 알맞은 위치에 저장되고 이로써 모든 정렬이 완료된다.
4단계: 배열 복사하기
정렬은 완료되었지만 정렬한 결과가 저장되는 것은 작업용 배열 b이므로 배열 a는 정렬하기 전의 상태이다. 그러므로 아래의 for 문을 수행하여 배열 b의 모든 원소를 배열 a에 그대로 복사한다.
for i in range(n):
a[i] = b[i]
도수 정렬은 if 문을 사용하지 않고 for 문만 반복해서 정렬할 수 있는 알고리즘이다.
아래 프로그램은 이러한 도수 정렬을 수행하는 프로그램이다.
# 도수 정렬 알고리즘 구현하기
from typing import MutableSequence
def fsort(a: MutableSequence, max: int) -> None:
"""도수 정렬(배열 원솟값은 0 이상 max 이하)"""
n = len(a) # 정렬할 배열 a
f = [0] * (max + 1) # 누적 도수 분포표 배열 f
b = [0] * n # 작업용 배열 b
for i in range(n): f[a[i]] += 1 # [1단계]
for i in range(1, max + 1): f[i] += f[i - 1] # [2단계]
for i in range(n - 1, -1, -1): f[a[i]] -= 1; b[f[a[i]]] = a[i] # [3단계]
for i in range(n): a[i] = b[i] # [4단계]
def counting_sort(a: MutableSequence) -> None:
"""도수 정렬"""
fsort(a, max(a))
if __name__ == '__main__':
print('도수 정렬을 수행합니다.')
num = int(input('원소 수를 입력하세요.: '))
x = [None] * num # 원소 수가 num인 배열을 생성
for i in range(num): # 양수만 입력받도록 제한
while True:
x[i] = int(input(f'x[{i}]: '))
if x[i] >= 0: break
counting_sort(x) # 배열 x를 도수 정렬
print('오름차순으로 정렬했습니다.')
for i in range(num):
print(f'x[{i}]: {x[i]}')
실행 결과
도수 정렬을 수행합니다.
원소 수를 입력하세요.: 7
x[0]: 22
x[1]: 5
x[2]: 11
x[3]: 32
x[4]: 99
x[5]: 68
x[6]: 70
오름차순으로 정렬했습니다.
x[0]: 5
x[1]: 11
x[2]: 22
x[3]: 32
x[4]: 68
x[5]: 70
x[6]: 99
Process finished with exit code 0
fsort( ) 함수는 도수 정렬을 수행한다. 배열의 모든 원솟값이 0 이상 max 이하라는 것을 전제로 해서 배열 a를 정렬한다.
counting_sort( ) 함수는 배열 a와 그 원소의 최댓값 max(a)를 fsort( ) 함수에 전달하여 호출한다. 실행 결과를 보면 원소의 최댓값이 99이므로 호출식 fsort(a, max(a))는 fsort(a, 99)가 된다.
메인 함수 내 for 문에서는 입력 받는 값을 0 이상의 값(양수)으로 제한한다.
08~09행: fsort( ) 함수 안의 앞부분에서는 두 배열 f와 b를 생성한다. 앞에서 살펴본 것과 같이 배열 f는 도수 분포와 누적 도수를 저장하는 배열이고, 배열 b는 정렬한 배열을 임시로 저장하는 작업용 배열이다. 두 배열의 전체 원솟값을 0으로 초기화한다.
배열 f는 0~max인 원소가 필요하므로 원소 수는 max + 1이다. 또 배열 b는 정렬 결과를 임시로 저장하는 배열이므로 원소 수는 배열 a와 같은 n이다.
11~14행: fsort( ) 함수는 4단계로 구성된다. 1~4단계까지 각 단계별 내용은 지금까지 학습한 도수 정렬의 단계와 같다.
도수 정렬 알고리즘은 데이터 비교·교환 작업이 필요 없어 매우 빠르다. 프로그램에서는 단일 for 문만 사용하고 재귀 호출이나 이중 if 문이 없어 매우 효율이 좋은 알고리즘이다. 하지만 도수분포표가 필요하므로(예를 들어 0, 1, ..., 100점인 시험 점수와 같이) 데이터의 최솟값과 최댓값을 미리 알고 있는 경우에만 적용할 수 있다.
fsort( ) 함수는 배열 a의 원솟값이 0 이상 max 이하인 것을 전제로 한다.
각 단계(for 문)에서 배열 원소를 건너뛰지 않고 순서대로 스캔하므로 이 정렬 알고리즘은 안정적이다.
그러나 3단계에서 배열 a를 스캔할 때 맨 앞부터 스캔하면 안정적이지 않다는 점을 주의해야 한다.
맨 앞에서 맨 끝을 향해 스캔하면 안정적이지 않은 이유는 같은 키값의 순서 관계가 정렬 전후로 뒤바뀌기 때문이다.