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

07 {
08 int i;
09 int *f = calloc(max + 1, sizeof(int)); /* 누적 도수 */
10 int *b = calloc(n, sizeof(int)); /* 작업용 목적 배열 */
11
12 for(i = 0; i <= max; i++) f[i] = 0; /* [Step0] */
13 for(i = 0; i < n; i++) f[a[i]]++; /* [Step1] */
14 for(i = 1; i <= max; i++) f[i] += f[i – 1]; /* [Step2] */
15 for(i = n - 1; i >= 0; i--) b[--f[a[i]]] = a[i]; /* [Step3] */
16 for(i = 0; i < n; i++) a[i] = b[i]; /* [Step4] */
17
18 free(b);
19 free(f);
20 }
21
22 int main(void)
23 {
24 int i, nx;
25 int *x; /* 배열의 첫 번째 요소에 대한 포인터 */
26 const int max = 100; /* 가장 큰 값 */
27 puts("도수 정렬");
28 printf("요소 개수 : ");
29
30 scanf("%d", &nx);
31 x = calloc(nx, sizeof(int));
32 printf("0 ~ %d의 정수를 입력하세요.\n", max);
33 실행 결과
34 for(i = 0; i < nx; i++) { 도수 정렬
35 do { 요소 개수 : 7
36 printf("x[%d] : ", i); 0 ~ 100의 정수를 입력하세요.
37 scanf("%d", &x[i]); x[0] : 22
x[1] : 5
38 } while(x[i] < 0 || x[i] > max);
x[2] : 11
39 }
x[3] : 32
40
x[4] : 98
41 fsort(x, nx, max); /* 배열 x를 도수 정렬 */ x[5] : 68
42 puts("오름차순으로 정렬했습니다."); x[6] : 70
43 오름차순으로 정렬했습니다.
44 for(i = 0; i < nx; i++) x[0] = 5
45 printf("x[%d] = %d\n", i, x[i]); x[1] = 11
46 x[2] = 22
47 free(x); /* 배열을 해제 */ x[3] = 32
48 x[4] = 68
x[5] = 70
49 return 0;
x[6] = 98
50 }

270 C 알고리즘