BohYoh.comトップページへ

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

戻る  

演習6-3の解答

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

/* 演習6-3 単純交換ソート(第2版:交換回数による打ち切り) */ #include <stdio.h> #define swap(type, x, y) do {type t = x; x = y; y = t; } while (0) /*--- 単純交換ソート(第2版:交換回数による打ち切り) ---*/ void bubble(int a[], int n) { int i, j, m; int ccnt = 0; /* 比較回数 */ int scnt = 0; /* 交換回数 */ for (i = 0; i < n - 1; i++) { int exchg = 0; /* パスにおける交換回数 */ printf("パス%d:\n", i + 1); for (j = n - 1; j > i; 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]); exchg++; scnt++; } } for (m = 0; m < n; m++) printf("%3d " , a[m]); putchar('\n'); if (exchg == 0) break; /* 交換が行われなかったら終了 */ } 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); }


戻る