BohYoh.comトップページへ

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

戻る  

演習6-9の解答

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

/* 演習6-9(その2) シェルソート(第2版:h = …, 13, 4, 1) */ #include <stdio.h> #define swap(type, x, y) do {type t = x; x = y; y = t; } while (0) /*--- シェルソート(第2版: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); }


戻る