低速アルゴリズム

 

バブルソート ( Bubblesort )

 バブルソートは単純選択ソートを少し変形したもので、最小値を求めることをせずに、左から順に隣会った左右のデータを比べ、左側のデータが大きい時にはすぐに入れ換えを行なう方法である。
バブルとは泡を意味していて、データが下から上へ泡立つ(左から右へ順に大きくなる)ように並べ換えが行なわれることから、泡立ち法とも呼ばれている。下記の例で、その動きを見よう。
  49   66   11   37   84    6   22   73
 
まず、49と66を比べ49の方が小さいのでなにもしない。
  49   66   11   37   84    6   22   73
 
続いて、66と11を比べ11の方が小さいので11と66を入れ換える。
  49   11   66   37   84    6   22   73
 
さらに、66と37を比べ37の方が小さいので66と37を入れ換える。
   49   11   37   66   84    6   22   73
                          ・
                          ・
                          ・
 
以下、一番右のデータまで繰り返す。
   49   11   37   66    6   22   73   84
 
すると、一番右側に最大のデータがくる。上記の操作を、左から順に右から2番目までのデータに対して行なう。
    11   37   49    6   22   66   73   84
 
すると、右から2番目には2番目に大きいデータがくる。このように、上記操作を続けると最後には左から昇順にデータは並ぶことになる。
   6   11   22   37   49   66   73   84
 
上記のデータの動きからも、泡立つ様子がうかがえたことでしょう。
この考えを取り入れたプログラミングが次のプログラムである。
 
 1 :  void BublleSort(int data[], int n) {
 2 :  	int tmp, i, j;
 3 : 
 4 : 	for (i=0; i < n-1; i++)
 5 : 		for (j=0; j < n-i-1; j++)
 6 : 			if(data[j] > data[j+1]) {
 7 : 				tmp = data[j];
 8 : 				data[j] = data[j+1];
 9 :  				data[j+1] = tmp;
10 :   			}
11 :  }
 ここで、各実行文の実行回数を評価してみよう。評価結果は以下のようである。
  4行目             n     回
  5行目  (n−1)*n/2 回  ((n−1)+(n−2)+・・・+1)
  6行目  (n−1)*n/2 回
  7行目  (nー1)*n/4 回
  8行目  (nー1)*n/4 回
  9行目  (nー1)*n/4 回
 
よって、バブルソートも単純選択ソートと同様O(n^2)の計算量を持つことが分かる。

戻る

アプレットに戻る

a93sj030@j.dendai.ac.jp