バブルソートによるソーティング

ソーティング（並べ替え）とは、データを大きい順（降順）、あるいは小さい順（昇順）に並べ替える処理です。処理自体は単に順に並ベ変えていくだけなのですが、その方法によって処理効率が大きく変わる上、プログラムも比較的わかりやすいため、「アルゴリズム」の話題では必ず出てきますね。

今回は、最も単純なソートアルゴリズムの一つである「バブルソート」を試してみることにしましょう。

バブルソートのアルゴリズム

バブルソートは、「隣と比較して昇順／降順に入れ替える」処理を繰り返すことで全体を並べ替えます。

具体的には、小さい順に並べ替えるなら隣と比べて大きい方を後ろへ持ってくる、という事を繰り返して一番大きいものを一番後ろへ持っていき、その処理をする範囲をだんだん前の方へ狭めていきます。つまり、大きい順に後ろに持っていく事で前から「小さい順」に並べ替えるわけです。

バブルソートではデータの比較や代入の処理回数（プログラムの計算量）が多くなりやすいことから、ソート対象のデータが多くなってくると処理速度が大きく低下する傾向があります。ただ、データの数がそれほど多くなければ実用上あまり問題にはなりません。

実際、数十件から数百件程度のデータを並べ替える場合には実装の容易さも含めバブルソートが適している場面も多いことでしょう。

バブルソートの処理を実際のデータを並べ替えながら追っていくことにします。

まず、最も大きいものを一番後ろに持っていく処理から考えてみましょう。
これには、あるデータとその１つ後ろのデータを比べて後ろのデータの方が小さければ、そのデータを前に持ってくる、という処理を行います。これを１番前から１つづつ後ろにずらして繰り返していくと、大きいデータが次々に後ろに送られて処理をした範囲の中で最も大きなデータが、最も後ろに置かれる事がわかるでしょう。

つまり、これを最初から始めて最後から１つ前のデータまで繰り返すと、その中で最も大きなデータが最後に置かれる事になります。

・例（７、８、３、５というデータの例）

・１回目

　　７　８　３　５
　　↑　↑
　　後ろの方が大きいのでそのまま

・２回目

　　７　８　３　５････その結果　７　３　８　５ となる
　　　　↑　↑
　　　後ろの方が小さいので入れ替える

・３回目

　　７　３　８　５････その結果　７　３　５　８ となる
　　　　　　↑　↑
　　　　　後ろの方が小さいので入れ替える

これで、最も大きな８を一番後ろに持ってくる事が出来ました。
次は、最後の（すでに確定した）８を除いた７、３、５に対して同じ事をします。

一番最後に最も大きなデータを持ってこれたら、次は２番目に大きなデータを最後から２番目に持ってきましょう。そのためには入れ替えの処理を最初から始めて、最後から２つ前とその後ろ（最後から２番め）までで止めればよいですね。後は、同様の処理をデータ全体で繰り返すだけ。

バブルソートのプログラム

バブルソートのやり方（アルゴリズム）を確認できたので、処理手順をプログラムにまとめてみましょう。

バブルソートのアルゴリズムを実現するプログラムは、以下のような感じになります。

これは、int型データ配列の先頭アドレスとソートするデータの個数を引数として渡すと、その配列を並べ替えるプログラムです。

void BubbleSort(int dat[],int n) { /*渡された配列をバブルソートでソート*/

	int i,j,work;

	for (i=0;i<n-1;i++) /*範囲を狭めていく*/
		for (j=0;j<n-i-1;j++) /*先頭から順に処理*/

			if (dat[j]>dat[j+1]) { /*隣の方が小さいか？*/

				work=dat[j];  /*小さければ交換*/
				dat[j]=dat[j+1];
				dat[j+1]=work;

			}

}

このソースコードでは、大きなデータを最後の方に持っていきましたが、当然小さなデータを最初の方に持ってきてもソートできます。その場合は、比較・交換は最後の方から前の方に向けて行い、小さいデータを前に持っていくことになりますね。

バルブソートのアルゴリズムでは、処理対象の範囲すべてについて要素を一つずつ比較しながら最後尾の順序を確定し、続いて処理対象を一つ狭めて同じ処理を繰り返していきます。そのためバブルソートの計算量は、要素数の二乗に比例して増大する性質があります（O²）。