バブルソートをプログラミングする
言葉だけで説明するとわかりづらいことも、カードで実際に試せばすんなりと頭に入ってくるはずです。では、その手順をプログラムにしてみましょう。基本構造が直接選択法の裏返しだということがわかります。
手順を整理する
バブルソートの手順を整理しておきましょう。
・前提
(1) n枚のカードについて処理を行なう。
(2) 各カードを「項」と呼ぶ。
(3) (2)より、項番号は0からn-1番までとなる。
(4) 項の集合を「群」と呼ぶ。
・処理
未処理の項数をmとする
以下の処理を、処理対象が項n-2と項n-1になるまで繰り返す。
以下の処理を、処理対象が項0と項1になるまで(m=2になるまで)繰り返す。
項m-1の値と項m-2の値を比較する。
項m-1の値が項m-2の値より小さければ、両項の値を交換する。
直接選択法の場合と同じように、二重のループ構造となることがわかります。処理の進み方が最後尾から先頭に向かう点を除けば、両者の構造は実はそれほど大きく変わりません。
同じ結果に異なるアプローチ
ソースはリスト1のようになります。今回は、ループを繰り返すたびに配列の中身を表示し、処理過程がわかるようにしてみました。
実行結果は画面1のようになります。
得られる結果は同じでも、そこに至る過程には様々なアプローチがあります。ほんの少し視点を変えるだけで、思わぬ方法が見付かるかもしれません。
本コラムでは、整列と探索というアルゴリズムの基本に絞って紹介しましたが、業務や研究で用いるアプリケーションの開発過程でも、データ構造や処理手順に工夫を凝らす必要が生じることもあるでしょう。そのようなときに、パズルを解くような気持ちで挑んでみてください。
リスト1：バブルソートのサンプル～ex55-01.c
#include <stdio.h>
/* 元の配列（6個） */
int array[] = {6, 3, 2, 7, 1, 4};
/* 配列の中身を表示 */
void showarray(int ary[])
{
int i;
for (i=0; i<6; i++) {
printf("%d", ary[i]);
}
printf("¥n");
}
/* 値の入れ替え */
void swap(int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
/* --------
main
-------- */
int main(void)
{
int i, j;
/* 外側のループ -- 1巡ごとに対象が減っていく */
for(i=0; i<6-1; i++)
{
printf("%d 順目...¥n", i+1);
/* 内側のループ -- 最後尾から比較 */
for(j=6-1; j>i; j--)
{
/* 1つ前より小さければ入れ替える */
if( array[j] < array[j-1] ) {
swap(&(array[j]), &(array[j-1]));
}
/* 配列の値を表示 */
showarray(array);
}
}
printf("最終結果 : ");
showarray(array);
return(0);
}
あとがき
永らく続けてまいりました「もう一度基礎からC言語」ですが、今回で区切りを付けることとなりました。ご愛読いただいたみなさんに深く感謝いたします。ありがとうございました。
またどこかでお会いできることを祈って……。
長谷川裕行
|
|
|
TOP