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

演習6-9の解答

　要素の移動回数をカウントするように第2版のプログラムを改良せよ。さらに、いろいろな配列に対してプログラムを実行し、移動回数の比較を行ってみよ。

/*
    演習6-9（その２）
    シェルソート（第２版：h ＝ …, 13, 4, 1）
*/

#include  <stdio.h>

#define swap(type, x, y)    do {type t = x; x = y; y = t; } while (0)

/*--- シェルソート（第２版：h ＝ …, 13, 4, 1） ---*/
int ssort(int a[], int n)
{
    int  i, j, h;
    int  count = 0;                 /* 移動回数 */

    for (h = 1; h < n / 9; h = h * 3 + 1)
        ;

    for ( ; h > 0; h /= 3)
        for (i = h; i < n; i++) {
            int  tmp = a[i];
            for (j = i - h; j >= 0 && a[j] > tmp; j -= h) {
                a[j + h] = a[j];
                count++;
            }
            a[j + h] = tmp;
            count++;
        }
    return (count);
}

int main(void)
{
    int  i;
    int  x[7];
    int  nx = sizeof(x) / sizeof(x[0]);
    int  count = 0;             /* 移動回数 */

    printf("%d個の整数を入力せよ。\n", nx);
    for (i = 0; i < nx; i++) {
        printf("x[%d] : ", i);
        scanf("%d", &x[i]);
    }

    count = ssort(x, nx);           /* 配列xをシェルソート */

    puts("昇順にソートしました。");
    for (i = 0; i < nx; i++)
        printf("x[%d] = %d\n", i, x[i]);
    printf("要素の移動回数は%d回でした。", count);

    return (0);
}

戻る