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

남은 작업은 배열의 각 요솟값과 누적도수분포표 f를 대조하여 정렬을 마친 배열을 만드는 작

업입니다. 이 작업은 배열 a와 같은 요소의 개수를 갖는 작업용 배열 b가 필요합니다. 그러면
배열 a의 요소를 마지막 위치부터 처음 위치까지 스캔하면서 배열 f와 대조하는 작업을 수행
하겠습니다.

마지막 요소(a[8])의 값은 3입니다. 누적도수를 나타내는 배열(f[3])의 값이 5이므로 0~3점 사
이에 5명이 있음을 알 수 있습니다. 목적 배열인 b[4]에 3을 저장합니다. 조금 복잡해 보이는
과정이지만 그림을 잘 살펴보면서 이해하세요.

❹
❸ ３
b[--f[a[i]]] = a[i];

０ １ ２ ３ ４ ５ ６ ７ ８
a 5 7 0 2 4 10 3 1 3

０ １ ２ ❸ ４ ５ ６ ７ ８ ９ １０
f 1 2 3 5 6 7 7 8 8 8 9

０ １ ２ ３ ❹ ５ ６ ７ ８ 3점은 5번째 값이므로 5번째
b 3 위치인 b[4]에 값 3을 저장합니다.

[그림 6-40] 목적 배열 만들기(1)

이 작업을 할 때 f[3]의 값을 5에서 1만큼 감소시켜 4로 만듭니다. 이 이유도 좀 더 있다가 설
명하겠습니다. 그런 다음 바로 앞의 요소인 a[7]의 값은 1입니다. 누적도수를 나타내는 f[1]
의 값(2)은 0~1점 사이에 2명이 있음을 의미합니다. 따라서 작업용 목적 배열 b[1]에 1을 저

장합니다.
배열의 2번째 요소는 인덱스가 1입니다. 따라서 이 작업을 할 때도 f[1]의 값을 2에서 1만큼 감소시켜 1로 만듭니다.

❶
❶ １
b[--f[a[i]]] = a[i];

０ １ ２ ３ ４ ５ ６ ７ ８
a 5 7 0 2 4 10 3 1 3

０ ❶ ２ ３ ４ ５ ６ ７ ８ ９ １０
f 1 2 3 4 6 7 7 8 8 8 9

０ ❶ ２ ３ ４ ５ ６ ７ ８ 1점은 2번째 값이므로 2번째
b 1 3 위치인 b[1]에 값 1을 저장합니다.

[그림 6-41] 목적 배열 만들기(2)

268 C 알고리즘