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

2단계 누적도수분포표 만들기

도수분포표를 만든 다음에 ‘0점부터 점수 n까지 몇 명의 학생이 있는지’ 누적된 값을 나타내
는 누적도수분포표를 만들어 보겠습니다. 그림 6-39에 배열 f의 두 번째 요소부터 바로 앞의
요솟값을 더하는 과정을 나타냈습니다. 가장 마지막 그림이 누적도수분포표의 완성된 모습
입니다.

예를 들어, f[4]의 값(6)은 0~4점을 받은 학생이 6명임을 의미하고, f[10]의 값(9)은 0~10점을 받은 학생이 9명임을 의
미합니다.

for(i = 1; i <= max; i++)
f[i] += f[i - 1];

０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０
1 1 1 2 1 1 0 1 0 0 1
f[1] += f[0];
1 2 1 2 1 1 0 1 0 0 1
f[2] += f[1];
1 2 3 2 1 1 0 1 0 0 1
f[3] += f[2];
1 2 3 5 1 1 0 1 0 0 1
f[4] += f[3];
1 2 3 5 6 1 0 1 0 0 1
f[5] += f[4];
1 2 3 5 6 7 0 1 0 0 1
f[6] += f[5];
1 2 3 5 6 7 7 1 0 0 1
f[7] += f[6];
1 2 3 5 6 7 7 8 0 0 1
f[8] += f[7];
1 2 3 5 6 7 7 8 8 0 1
f[9] += f[8];
1 2 3 5 6 7 7 8 8 8 1
f[10] += f[9];
1 2 3 5 6 7 7 8 8 8 9

[그림 6-39] 누적도수분포표 만들기

3단계 목적 배열 만들기
각각의 점수를 받은 학생이 몇 번째에 위치하는지 알 for(i = n - 1; i >= 0; i--)
b[--f[a[i]]] = a[i];
수 있으므로 이 시점에서 정렬은 거의 마쳤다고 할 수
있습니다.
06•정렬 267