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

배열 a에서의 스캔을 계속하겠습니다. 다음에 살펴볼 값은 a[6]입니다. 이때 a[8]에서 3점 학

생을 배열 b에 저장하는 과정을 이미 한 번 진행했기 때문에 두 번째로 진행해야 합니다. 이때
a[8]의 값(3)을 목적 배열에 넣을 때 f[3]의 값을 1만큼 감소시켜 4로 만들었음을 기억하세요.

이렇게 미리 값을 감소시켰기 때문에 중복되는 값인 3을 목적 배열의 4번째 요소(b[3])에 저

장할 수 있습니다. 정렬하기 전 배열의 뒤쪽 요소 a[8]이 b[4]에 저장되고, 앞쪽 요소 a[6]이 b[3]에 저장됩니다.

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

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

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

０ １ ２ ❸ ４ ５ ６ ７ ８ 3점은 4번째 값이므로 4번째 위
b 1 3 3 치인 b[3]에 값 3을 넣습니다.
[그림 6-42] 목적 배열 만들기(3)

위의 작업을 a[0]까지 진행하면 배열 a의 모든 요소를 배열 b의 알맞은 위치에 저장할 수 있

습니다.

4단계 배열 복사하기
정렬은 끝났지만 정렬 결과를 저장한 곳은 작업 배열 for(i = 0; i < n; i++)
a[i] = b[i];
(b)입니다. 배열 a는 정렬하기 전 상태이므로 배열 b
값을 배열 a로 복사해야 합니다.

도수 정렬은 if문 대신 for문만을 사용해 정렬할 수 있는 매우 아름다운 알고리즘입니다. 실습
6-16은 도수 정렬 프로그램입니다.

실습 6-16 •완성 파일 chap06/fsort.c
01 /* 도수 정렬 프로그램 */
02 #include <stdio.h>
03 #include <stdlib.h>
04
05 /*--- 도수 정렬 함수(배열의 요솟값은 0 이상 max 이하입니다) ---*/
06 void fsort(int a[], int n, int max)

06•정렬 269