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

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

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

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

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

シノ

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

単純なソートアルゴリズムの一つ「バブルソート」
バブルソートの計算量
バブルソートのサンプルプログラム
おわりに

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

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

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

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

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

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

iを0からn-2まで1つずつ増やしながら、以下を繰り返す
1. jをn-1からi+1まで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

ソート途中経過1

この状態で、更に次へ。

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

i	0	1	2	3	4	5
data[i]	5	1	3	4	2	6

ソート途中経過2

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

i	0	1	2	3	4	5
data[i]	1	5	3	4	2	6

ソート途中経過3

このとき、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

ソート途中経過4

i	0	1	2	3	4	5
data[i]	1	2	3	5	4	6

ソート途中経過5

i	0	1	2	3	4	5
data[i]	1	2	3	4	5	6

ソート途中経過6

i	0	1	2	3	4	5
data[i]	1	2	3	4	5	6

ソート途中経過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;
            }
        }
    }
}