最近、このブログに「バブルソート」とか具体的なソート名の検索で見てくださっている方がいらっしゃるようだ。
なので、単体で解説をしていこう。
今回は、単純なソートアルゴリズムの一つである「バブルソート」をご紹介する。
基本的なものなので、何をしているか、しっかり把握してほしい。
分からなくなったら、
一個ずつ慎重に処理を追っていこう！
単純なソートアルゴリズムの一つ「バブルソート」
これは、二つの隣接したデータを比較しながら、逆順であれば入れ替えるということを繰り返すアルゴリズムだ。
先に、アルゴリズム全体を。
入力はdata配列、添え字0～n-1までのn要素を持つとしよう。
出力もdata配列で、中身はソート済みとする。
この場合のバブルソートアルゴリズムは、以下の通りだ。
iを0からn-2まで1つずつ増やしながら、以下を繰り返すjをn-1からi+1まで1つずつ減らしながら、以下を繰り返すdata[j - 1] > data[j]なら、この2つを入れ替える
dataを出力する
これだけだと分かりづらいので、具体的な数値で見てみよう。
以下のような6個の要素を持つ配列をソートしていく。
| i | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| data[i] | 5 | 3 | 4 | 1 | 2 | 6 |
では、まず変数iを用意し、0から見ていく。
ここで、j=n-1=5とし、更に次に進もう。
data[j-1]=data[4]と、data[j]=data[5]を比較する。
今、2と6なので、data[4] < data[5]となっているからそのままだ。
次に、jを1減らして、また見ていく。
今度も、1と2でdata[3] < data[4]となっている、変化なし。
次に、やっと変化が起こる。
再度jを1減らし、今jは3だ。
つまり、data[2]とdata[3]を比較する。
data[2] = 4、data[3] = 1なので、今度はdata[2] > data[3]だ。
よって、この二つを入れ替えよう。
| i | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| data[i] | 5 | 3 | 1 | 4 | 2 | 6 |
この状態で、更に次へ。
data[1] > data[2]なので、ここも入れ替え。
| i | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| data[i] | 5 | 1 | 3 | 4 | 2 | 6 |
最後、data[0] > data[1]なので、同じく入れ替える。
| i | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| data[i] | 1 | 5 | 3 | 4 | 2 | 6 |
このとき、j=1でi=0、つまりj=i+1となったので、iの一回目のループが終了となる。
さて、このときのデータに注目してみよう。
先頭に、一番小さいデータ1が来ているのが分かるだろうか。
つまり、1回のループで、先頭の要素がソート済みとなる。
このように、小さい数が上がってくることから、バブル(泡)のようなのでバブルソートと呼ぶのだ。
あとは、範囲を一個ずつ狭めて、同じことを最後までしてあげればいい。
参考までに、iのループが終わるごとの途中経過を出しておこう。
太字がすでにソート済みの範囲、赤字が新たにソートされた箇所だ。
| i | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| data[i] | 1 | 2 | 5 | 3 | 4 | 6 |
| i | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| data[i] | 1 | 2 | 3 | 5 | 4 | 6 |
| i | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| data[i] | 1 | 2 | 3 | 4 | 5 | 6 |
| i | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| data[i] | 1 | 2 | 3 | 4 | 5 | 6 |
これで、n-1個の並び替えが終わった状態だ。
実は、この時点でソート完了となる。
というのも、最後に残っているのは1個なので、それもソート済みと見なせるのだ。
以上が、バブルソートの流れだ。
なお、このバブルソートは、安定なソートだ。
安定とは、並び替えるときに同じキーがあった場合に、元の順番を保持するかどうかという考え方。
安定ならば、元の順番が保持される。
安定でないならば、その箇所の並びについては保証されない。
例えば、並び替えるときに、5という数字が二つ出ていたとしよう。
このとき、安定ならば、元の5の出てくる順番でソートがされる。
しかし、安定でないなら、この5は前後どちらになるか分からないのだ。
この、安定である必要があるかどうかも重要な確認項目なので、条件を忘れずにチェックしてほしい。
バブルソートの計算量
次に、バブルソートの計算量を見ていこう。
先に、心配な方は計算量も解説しているので、そちらをご参照頂きたい。
計算量とは？プログラムの性能を計ってみよう | Shino’s Mind Archive
まず、計算回数を全部足してみる。
データ数をnとすると、1回目のiのループでn-1回、2回目でn-2回、…、n-1回目で1回と計算をしている。
つまり、比較の合計は、
$$(n – 1) + (n – 2) + … + 2 + 1 = \frac{n(n – 1)}{2}$$
と計算できる。
次に、条件に合致したら入れ替える処理だが…これは定数倍なので、計算量的には無視できる。
というわけで、上の式を整理すれば、計算量が出てくるのだ。
まず、括弧を外そう。
$$\frac{n(n – 1)}{2} = \frac{n^2}{2} – \frac{n}{2}$$
計算量の足し算(引き算)では、大きい方を残すので…
$$O(\frac{n^2}{2} – \frac{n}{2}) = O(\frac{n^2}{2})$$
最後、計算量では定数倍を無視するので…
$$O(\frac{n^2}{2}) = O(n^2)$$
つまり、バブルソートの計算量は\(O(n^2)\)となる。
バブルソートのサンプルプログラム
最後に、参考までにバブルソートを行うプログラムを載せておこう。
言語はJavaScriptで書いているが、他の言語でもほぼ同じ形で書けるはずだ。
function bubble_sort(arr){
var n = arr.length;
for(var i = 0; i < n - 1; i++){
for(var j = n - 1; j > i; j--){
if(arr[j - 1] > arr[j]){
var tmp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = tmp;
}
}
}
}おわりに
今回は、バブルソートを解説した。
単純なソートアルゴリズムの中でも特に簡単なものなので、動きをしっかり把握しておこう。
今後、同じように選択ソート、挿入ソートも解説しようと思う。
コメント