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

戻る  

演習6-18の解答

/*
    演習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);
}

戻る