BohYoh.comトップページへ

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

戻る  

演習6-5の解答

 以下に示すデータの並びをソートすることを考えよう。
  9 1 3 4 6 7 8
 ほぼソート済みであるにも関わらず、最大の要素9が先頭に位置しているために、第3版のアルゴリズムでも、ソート作業を早期に打ち切ることはできない。というのも、最大の要素は、各パスにおいて、一つずつしか後ろに移動しないためである。
 そこで、奇数パスでは最小要素を先頭側に移動させ、偶数パスでは最大要素を末尾側に移動するというように、パスを交互に行えば、このような並びを高速にソートできるはずである。バブルソートを改良したこのアルゴリズムは、双方向バブルソートbidirection bubble sort )あるいはシェーカーソートshaker sort )という名称で知られている。
 第3版を改良して、双方向バブルソートを行うプログラムを作成せよ。

/* 演習6-5 シェーカーソート */ #include <stdio.h> #define swap(type, x, y) do {type t = x; x = y; y = t; } while (0) void shakersort(int a[],int n) { int left = 0; int right = n - 1; int last = right; while (left < right){ int j; for (j = right; j > left; j--){ if (a[j - 1] > a[j]){ swap(int, a[j - 1], a[j]); last = j; } } left = last; for (j = left; j < right; j++){ if (a[j] > a[j + 1]){ swap(int, a[j], a[j + 1]); last = j; } } right = last; } } 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]); } shakersort(x, nx); /* 配列xをシェーカーソート */ puts("昇順にソートしました。"); for (i = 0; i < nx; i++) printf("x[%d] = %d\n", i, x[i]); return (0); }


戻る