3 バブルソート

3.1 手順とプログラム

ここは教科書を使って説明する．

このアルゴリズムの特徴は，

• もっとも値の大きいデータは，外側の1回のループで右端に移動する．
• 小さい値で，左に移動すべきデータは，一つずつしか移動できない．この一つず つしか移動できないので，整列に多くの計算回数が必要となる．
• 左に移動するデータのうち，初期位置と整列終了位置との差の最大なものにより， 計算回数は決まる．

3.2 計算量

教科書のアルゴリズム(プログラム)の計算量を計算する．このプログラムの計算量は，内 側のループの回数,すなわち，大小の比較回数

if(sort[i]>sort[i+1]) (1)

の実行回数で評価できるであろう．なにしろ，プログラム中もっとも実行回数の多い命令 は，この文であるからである．

この文の最小実行回数は，最初から整列できている場合である．このときの，実行回数は， $N-1$回であるのは明らかである．最悪の場合は，最小の値が右端にある場合である．こ の場合の実行回数は，$(N-1)^2$となる．なぜならば，

• この最小の値は，1回外側のループ(do文のところ)を実行する毎に，一つ左に移動する．
• 所定の位置に移動するために，$N-1$回，外側のループを実行する必要がある．
• 外側のループを1回実行する毎に，内側のループは$N-1$回，実行される．

となるからである．

最初のデータの並び方により，$N-1$回から$(N-1)^2$まで開きがある．初期位置と整列終 了位置との差の最大の期待値を計算することになるが，これが難しい．まだ，ちゃんとし た計算が出来ていないので，正確なことは言えないが，大体，それは$(N-2)/2$程度であ ることは分かるだろう．最小な値の初期位置と整列終了位置との差の期待値である．この 程度とすると，先の比較の実行回数は，

$$\frac{(N-1)(N-2)}{2}=\frac{N^2}{2}-\frac{3}{2}N+1$$ (2)

となる．データ数$N$が大きい場合，$N^2$に比例して計算量が増加する．

この$N^2$に比例して計算量が必要なばあい，$O(N^2)$と書く．この表記法を $O$記法($O$-notation)といい，計算オーダーを示す．数学で使うランダウの記 号に似ている．

かなりいい加減な説明で，バブルソートの計算回数が$O(N^2)$と示した．もっと正確に， 説明したかったが，計算方法を思いつかなかった．ネットでも正確な記述を見つけること が出来なかった．正確な計算方法が分かれば，もう一度，説明する．

3.3 まとめ

ここで示したように，バブルソートは$O(n^2)$の計算オーダーなので，次週で述べるクイッ クソートに比べて，効率の悪いアルゴリズムである．したがって，実際問題で，このソー トは使ってはならないとされている．ただ，アルゴリズムが単純なので，最初の学習に はちょうど良いので取り上げられるが，ただ，使い道はそれだけである．

ホームページ: Yamamoto's laboratory
著者: 山本昌志