BohYoh.comトップページへ

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

戻る  

演習6-4の解答

 演習6-2と同様に、比較・交換の様子が詳細に分かるように、第3版のプログラムを書きかえよ。

/* 演習6-4 単純交換ソート(第3版:走査範囲を限定) */ #include <stdio.h> #define swap(type, x, y) do {type t = x; x = y; y = t; } while (0) /*--- 単純交換ソート(第3版:走査範囲を限定) ---*/ void bubble(int a[], int n) { int i = 0, j, m; int ccnt = 0; /* 比較回数 */ int scnt = 0; /* 交換回数 */ int k = 0; /* a[k]より前はソート済み */ while (k < n - 1) { int j; int last = n - 1; /* 最後に交換した位置 */ printf("パス%d:\n", ++i); for (j = n - 1; j > k; j--) { for (m = 0; m < n - 1; m++) printf("%3d %c" , a[m], (m != j-1) ? ' ' : (a[j - 1] > a[j]) ? '+' : '-'); printf("%3d\n", a[n - 1]); ccnt++; if (a[j - 1] > a[j]) { swap(int, a[j - 1], a[j]); last = j; scnt++; } } k = last; for (m = 0; m < n; m++) printf("%3d " , a[m]); putchar('\n'); } printf("比較は%d回でした。\n", ccnt); printf("交換は%d回でした。\n", scnt); } int main(void) { int i; int x[7]; int nx = sizeof(x) / sizeof(x[0]); printf("%d個の整数を入力せよ。\n", nx); for (i = 0; i < nx; i++) { printf("x[%d] : ", i); scanf("%d", &x[i]); } bubble(x, nx); /* 配列xを単純交換ソート */ puts("昇順にソートしました。"); for (i = 0; i < nx; i++) printf("x[%d] = %d\n", i, x[i]); return (0); }


戻る