低速アルゴリズム
バブルソート ( Bubblesort )
バブルソートは単純選択ソートを少し変形したもので、最小値を求めることをせずに、左から順に隣会った左右のデータを比べ、左側のデータが大きい時にはすぐに入れ換えを行なう方法である。
バブルとは泡を意味していて、データが下から上へ泡立つ（左から右へ順に大きくなる）ように並べ換えが行なわれることから、泡立ち法とも呼ばれている。下記の例で、その動きを見よう。
49 66 11 37 84 6 22 73
まず、４９と６６を比べ４９の方が小さいのでなにもしない。
49 66 11 37 84 6 22 73
続いて、６６と１１を比べ１１の方が小さいので１１と６６を入れ換える。
49 11 66 37 84 6 22 73
さらに、６６と３７を比べ３７の方が小さいので６６と３７を入れ換える。
49 11 37 66 84 6 22 73
・
・
・
以下、一番右のデータまで繰り返す。
49 11 37 66 6 22 73 84
すると、一番右側に最大のデータがくる。上記の操作を、左から順に右から２番目までのデータに対して行なう。
11 37 49 6 22 66 73 84
すると、右から２番目には２番目に大きいデータがくる。このように、上記操作を続けると最後には左から昇順にデータは並ぶことになる。
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 : }
ここで、各実行文の実行回数を評価してみよう。評価結果は以下のようである。
４行目 ｎ 回
５行目 （ｎ−１）＊ｎ／２ 回 （（ｎ−１）＋（ｎ−２）＋・・・＋１）
６行目 （ｎ−１）＊ｎ／２ 回
７行目 （ｎー１）＊ｎ／４ 回
８行目 （ｎー１）＊ｎ／４ 回
９行目 （ｎー１）＊ｎ／４ 回
よって、バブルソートも単純選択ソートと同様Ｏ（ｎ＾２）の計算量を持つことが分かる。
戻る
アプレットに戻る
a93sj030@j.dendai.ac.jp