Page 266 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

06-9 도수 정렬

도수 정렬은 요소의 대소 관계를 판단하지 않고 빠르게 정렬할 수 있는 알고리즘입니다.

도수 정렬

지금까지의 정렬 알고리즘은 두 요소의 키 값을 비교해야 했습니다. 하지만 도수 정렬은 요소
를 비교할 필요가 없다는 특징이 있습니다. 그러면 10점 만점의 테스트에서 학생 9명의 점수

를 예로 들어 도수 정렬 알고리즘을 살펴보겠습니다(그림 6-38). 도수 정렬 알고리즘은 도수분
포표 작성, 누적도수분포표 작성, 목적 배열 만들기, 배열 복사의 4단계로 이루어집니다.
정렬하는 배열은 a, 요소의 개수는 n, 점수의 최댓값은 max입니다.

1단계 도수분포표 만들기
먼저 배열 a를 바탕으로 ‘각 점수에 해당하는 학생이 몇 명인지를 나타내는 도수분포표를 작

성합니다. 도수분포표를 나타내기 위해 배열 f를 사용합니다. 먼저 배열 f의 모든 요소의 값을
0으로 초기화합니다. 그런 다음 배열 a를 처음부터 스캔하면서 도수분포표를 만들면 됩니다.
a[0]은 5점이므로 f[5]를 1만큼 증가시킵니다. a[1]은 7점이므로 f[7]을 1만큼 증가시켜 1로

만듭니다. 이 작업을 배열 끝까지 반복하면 도수분포표가 완성됩니다.
예를 들어, f[3]의 값(2)은 3점을 맞은 학생이 2명이라는 뜻입니다.

for(i = 0; i < n; i++)
f[a[i]]++;
０ １ ２ ３ ４ ５ ６ ７ ８
a 5 7 0 2 4 10 3 1 3
０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０
f 0 0 0 0 0 0 0 0 0 0 0
５
0 0 0 0 0 1 0 0 0 0 0 f[a[0]]++;
７
0 0 0 0 0 1 0 1 0 0 0 f[a[1]]++;
０
1 0 0 0 0 1 0 1 0 0 0 f[a[2]]++;
…
중략
…
1 1 1 2 1 1 0 1 0 0 1

[그림 6-38] 도수분포표 만들기

266 C 알고리즘