| バブルソート |
多くのソートアルゴリズムの中で、直感的に最も理解しやすいのは、バブルソートでしょう。バブルとは「泡」のことで、並べ替えの過程でデータが下から上へ移動する様子が、泡が浮かんでいくように見えることからこの名前があります。
| 考え方 |
バブルソートのアルゴリズムは直感的であり、理解するのは容易です。
N個の数値データが、1個ずつ箱に入って並べてあります。ただし、数字はばらばらな順番で格納されているものとします。例えば、次のようです。
| 0 | 34 |
| 1 | 3 |
| 2 | 11 |
| 3 | 28 |
| ： | ： |
| N-1 | 17 |
バブルソートアルゴリズムを使ってこの数字を並べ替えるための、基本的な方針は次の通りです。
上の要素と比較し、上のほうが大きければ互いに交換する
これを、下から順番にやっていきます。そうすると、小さい数字は交換されて上に順々に上がってきます。一番下から一番上まで1回通ると、一番小さい数字が一番上に上がってきているはずです。
次に、一番上を除いて、もう1回同じことを繰り返します。そうすると、今度は2番目に小さい数字が2番目まで上がって来ます。（一番上は、操作から外れているので変化しません）
もう1回やると、3番目が上がってきます。
もう1回やると、4番目も上がってきます。以下、同様です。
最後までやれば、並べ替えは終了です。簡単ですね。
整数配列 a[ ] が与えられたとき、その中の値を昇順に並べ替えるバブルソートアルゴリズムを Java で書くと次のようになります。（これだけを打ちこんでも動きません。完全なプログラム例は、すぐ下に示します）
public void sort(int[] a){ // 最後の要素を除いて、すべての要素を並べ替えます for(int i=0;i<a.length-1;i++){ // 下から上に順番に比較します for(int j=a.length-1;j>i;j--){ // 上の方が大きいときは互いに入れ替えます if(a[j]<a[j-1]){ int t=a[j]; a[j]=a[j-1]; a[j-1]=t; } } } }【アルゴリズム1】 バブルソート
Java では、配列の要素数は a.length のようにして取り出すことができますから、特に要素数を指定する必要はありません。また、Java の配列は C と同じで 0 から始まりますから、N 個分のデータは a[0] 〜 a[N-1] となりますから注意しましょう。
| バブルソートの動作 |
バブルソートを可視化して行うアプレットを、下に示します。
このアプレットは、スタートするとランダムに並んだ長さの異なるデータを短い順に並べ替えます。この程度の並べ替えならば、たとえ遅いと言われるバブルソートを利用しても一瞬で終わってしまうのですが、並べ替えの過程を目で追えるようにスピードを調節できるようになっています。各部品の機能は以下の通りです。
部品 機能 "Start"ボタン ランダムなデータを作成して、並べ替えを開始します。一時停止中に押すと、再開します。 "Stop"ボタン 並べ替えを途中で停止します。 "Pause"ボタン 実行を一時停止します。再度押すと、再開します。 "1"〜"10" 1つのデータの幅を指定します。この数値が大きいとデータを表す帯の幅が広くなり、データ数が少なくなります。初期値は 10 です。 "VerySlow"〜"NoWait" 並べ替えのスピードを指定します。"NoWait" だと、一瞬で終わります。初期値は VerySlow です。 "Uniform"
"Overlap"
"Radix10"この選択項目は、並べ替えるデータをランダムに作成するときの、作成方法を指定します。初期値は "Uniform" です。
"Uniform" 順番に並んだデータ "Overlap" データ数よりもデータ値の種類が少なく、重複のあるデータ "Radix10" 10進数で3桁のデータ。データ数よりデータ値の種類の方が多く、飛び飛びになる
データは横長の長方形で表され、並べ替えの途中では黒で、並べ替えが終了すると赤で表示されます。
また、現在着目しているデータに赤線が、目標としている順番に青線が表示されますので、並べ替えがどこまで進んでいるかを一目で確認できます。
| 計算時間の評価 |
最後に、バブルソートに要する時間量について考えてみましょう。
バブルソートの基本となっている処理は、2つのデータの入れ替えです。【アルゴリズム1】のコードの中では、もっとも深いループの底の部分です。この処理を何回繰り返すかによって、バブルソートに要する時間量を評価することができます。
この回数を数えてみると、データ数を N として、
となりますから、合計、
(N-1) + (N-2) + (N-3) + … + 2 + 1 = N(N-1)/2
ということになります。この式には N の2乗が含まれていますから、オーダーとしては O(N2) ということになります。つまり、データ量が2倍、3倍に増えると、並べ替えに要する時間は4倍、9倍と増えていくと言うことです。
これは、並べ替えの方法としては速いほうではなく、他のソートアルゴリズムと比較してみるとわかりますが、むしろ非常に遅いです。
それゆえ、他のいろいろなソートアルゴリズムが考案されたとも言えます。