単純なソートアルゴリズム「バブルソート」を解説!

アルゴリズムとデータ構造講座

最近、このブログに「バブルソート」とか具体的なソート名の検索で見てくださっている方がいらっしゃるようだ。

なので、単体で解説をしていこう。

今回は、単純なソートアルゴリズムの一つである「バブルソート」をご紹介する。

基本的なものなので、何をしているか、しっかり把握してほしい。

シノ
シノ

分からなくなったら、
一個ずつ慎重に処理を追っていこう!

スポンサーリンク

単純なソートアルゴリズムの一つ「バブルソート」

これは、二つの隣接したデータを比較しながら、逆順であれば入れ替えるということを繰り返すアルゴリズムだ。

先に、アルゴリズム全体を。

入力はdata配列、添え字0~n-1までのn要素を持つとしよう。

出力もdata配列で、中身はソート済みとする。

この場合のバブルソートアルゴリズムは、以下の通りだ。

  1. i0からn-2まで1つずつ増やしながら、以下を繰り返す
    1. jn-1からi+1まで1つずつ減らしながら、以下を繰り返す
      1. data[j - 1] > data[j]なら、この2つを入れ替える
  2. dataを出力する

これだけだと分かりづらいので、具体的な数値で見てみよう。

以下のような6個の要素を持つ配列をソートしていく。

i012345
data[i]534126
ソートする配列

では、まず変数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] = 4data[3] = 1なので、今度はdata[2] > data[3]だ。

よって、この二つを入れ替えよう。

i012345
data[i]531426
ソート途中経過1

この状態で、更に次へ。

data[1] > data[2]なので、ここも入れ替え。

i012345
data[i]513426
ソート途中経過2

最後、data[0] > data[1]なので、同じく入れ替える。

i012345
data[i]153426
ソート途中経過3

このとき、j=1i=0、つまりj=i+1となったので、iの一回目のループが終了となる。

さて、このときのデータに注目してみよう。

先頭に、一番小さいデータ1が来ているのが分かるだろうか。

つまり、1回のループで、先頭の要素がソート済みとなる。

このように、小さい数が上がってくることから、バブル(泡)のようなのでバブルソートと呼ぶのだ。

あとは、範囲を一個ずつ狭めて、同じことを最後までしてあげればいい。

参考までに、iのループが終わるごとの途中経過を出しておこう。

太字がすでにソート済みの範囲、赤字が新たにソートされた箇所だ。

i012345
data[i]125346
ソート途中経過4
i012345
data[i]123546
ソート途中経過5
i012345
data[i]123456
ソート途中経過6
i012345
data[i]123456
ソート途中経過7

これで、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;
            }
        }
    }
}

おわりに

今回は、バブルソートを解説した。

単純なソートアルゴリズムの中でも特に簡単なものなので、動きをしっかり把握しておこう。

今後、同じように選択ソート挿入ソートも解説しようと思う。

コメント

タイトルとURLをコピーしました