低速アルゴリズム
バブルソート ( 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