BohYoh.comトップページへ

C言語によるアルゴリズムとデータ構造

戻る  

演習6-18の解答

 要素の値がmin以上max以下である要素数nの配列aを度数ソートする以下の関数を作成せよ。
  void fsort (int a [], int n , int min , int max );

/* 演習6-18 度数ソート */ #include <stdio.h> #include <stdlib.h> /*--- 度数ソート(配列要素の値はmin以上max以下) ---*/ void fsort(int a[], int n, int min, int max) { int i; int *f = (int *)calloc(max - min + 2, sizeof(int)); /* 累積度数 */ int *b = (int *)calloc(n, sizeof(int)); /* 作業用目的配列 */ for (i=0; i <= max-min+1; i++) f[i] = 0; /* 省略可 */ for (i=0; i < n; i++) f[a[i]-min]++; /* [Step1] */ for (i=1; i <= max-min+1; i++) f[i] += f[i - 1]; /* [Step2] */ for (i=n-1; i >= 0; i--) b[--f[a[i]-min]] = a[i]; /* [Step3] */ for (i=0; i < n; i++) a[i] = b[i]; free(b); free(f); } int main(void) { int i; int x[9]; int nx = sizeof(x) / sizeof(x[0]); const int min = 10; /* 最小値 */ const int max = 20; /* 最大値 */ printf("%d~%dの整数を%d個入力せよ。\n", min, max, nx); for (i = 0; i < nx; i++) { do { printf("x[%d] : ", i); scanf("%d", &x[i]); } while (x[i] < min || x[i] > max); } fsort(x, nx, min, max); /* 配列xを度数ソート */ puts("昇順にソートしました。"); for (i = 0; i < nx; i++) printf("x[%d] = %d\n", i, x[i]); return (0); }


戻る