バブルソート

多くのソートアルゴリズムの中で、直感的に最も理解しやすいのは、バブルソートでしょう。バブルとは「泡」のことで、並べ替えの過程でデータが下から上へ移動する様子が、泡が浮かんでいくように見えることからこの名前があります。

考え方

バブルソートのアルゴリズムは直感的であり、理解するのは容易です。

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倍と増えていくと言うことです。

これは、並べ替えの方法としては速いほうではなく、他のソートアルゴリズムと比較してみるとわかりますが、むしろ非常に遅いです。

それゆえ、他のいろいろなソートアルゴリズムが考案されたとも言えます。

← prev | next →