【バブル・選択・挿入ソート】単純なソートアルゴリズムの解説

これまで、そもそも論をひたすら書いてきた。

そもそも、アルゴリズムとデータ構造とは何か。

そもそも、計算量とは何か。

これらは、今後解説していく具体的な内容のために不可欠な要素だ。

というわけで、今回からその具体的な内容…まずは、単純なソートアルゴリズムと呼ばれているものから解説していこう。

前回までの内容…特に、計算量の感覚も、ここで掴んでいってもらいたい。

前回のお話

前回は、アルゴリズムを評価する上での指標となる計算量について解説した。

なかなか難しい話なので、前回の内容だけで完全に理解しきるのも難しいだろう。

今回以降で解説する具体的なアルゴリズムに当てはめて、理解を深めていってほしい。

ソートアルゴリズム

ソートアルゴリズムって何？

そもそも、ソートアルゴリズムとは、複数のデータを入力して、それを並び替えた結果を出力するアルゴリズムのことだ。

これには、大きく「単純なアルゴリズム」と、「高速なアルゴリズム」と呼ばれるものに分類される。

…実は、この中間に一つだけ「シェルソート」と呼ばれるアルゴリズムも存在する。これは、高速なアルゴリズムを解説するときに一緒に解説していこう。

単純なアルゴリズム

今回のタイトルにも入れたが、以下3つのソートアルゴリズムが該当する。

• バブルソート
• 選択ソート
• 挿入ソート

比較的単純な考え方なので、理解しやすいと思う。

高速なアルゴリズム

高速なアルゴリズムとは、その名の通り単純なアルゴリズムよりも高速に行うことができるアルゴリズムのことだ。

本講座では、上で名前を出したシェルソートと一緒に、後の回で以下を解説しようと思う。

• クイックソート
• マージソート
• ヒープソート

安定と不安定

さて、具体的なアルゴリズムに入る前に、ソート系のアルゴリズムで共通している言葉を定義しておこう。

「安定」、「不安定」というやつだ。

これは、整列する際に参照する部分が同じだった場合に、元の順番を保持するかどうかという考え方だ。

安定は、元の順番通りであることが保証されており、不安定はどうなるか分からない。

具体例を見ていこう。以下のような本のデータがあるとする。…タイトルが適当なのは許してほしい。

これらを、安い順でソートしたとしよう。

このとき、安定なソートだと、必ず以下のような結果になる。

値段1500円の2冊が、元の順番になっていると思う。

これに対し、不安定なソートだと、以下のような場合もあり得る。注意して欲しいのは、上とどちらになるか分からない、ということだ。

こちらは、1500円の2冊が元と順番が異なっている。

こうなってもいいかどうかというのも、注意しなければいけない項目の一つだろう。

単純なアルゴリズム

では、具体的なアルゴリズムの解説に入ろう。

なお、全部に共通していることとして、数字の配列arrを入力し、それを昇順に並び替えることとしよう。

また、配列arrの要素数をnとする。

バブルソート

バブルソートは、以下のようなアルゴリズムで行われる。一緒に、JavaScriptソースコードも出してしまおう。

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

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;
            }
        }
    }
}

iでどの範囲を並べ替えるかを決めて、jで後ろから一個ずつ実際に比較して並び替えている。

…と書いたが、言葉だけだと非常に分かりづらいので、具体例で見てみよう。

入力する配列を、[9, 2, 5, 7, 3]としてみる。

これで、まずはi=0の場合から。

• j=4のとき、arr[3] = 7とarr[4] = 3を比較
  →arr[3] > arr[4]なので、入れ替える　→　[9, 2, 5, 3, 7]
• j=3のとき、arr[2] = 5とarr[3] = 3を比較
  →arr[2] > arr[3]なので、入れ替える　→　[9, 2, 3, 5, 7]
• j=2のとき、arr[1] = 2とarr[2] = 3を比較
  →arr[1] > arr[2]ではないので、何もしない　→　[9, 2, 3, 5, 7]
• j=1のとき、arr[0] = 9とarr[1] = 2を比較
  →arr[0] > arr[1]なので、入れ替える　→　[2, 9, 3, 5, 7]

こんな感じだ。小さい数がだんだんと手前側に浮き上がってきているのが分かるだろうか。

これが、水中を上に浮かぶ泡のようなので、バブルソートと呼ばれている。

で、iの一回目のループが終わると、一番小さい数が一番左に来ている。この例で言えば、2が先頭に来ている。

この時点で、先頭1個は整列完了だ。

あとは、これと同じことを、今度は添え字1以降で、添え字2以降で…添え字i以降で、と順番にやってあげればいい。

並び変わっている様子を以下に書いてみよう。

未整列部分が1個残っているが、一番大きいものが1個残っているという時点でもう並び替えできているとみなせるだろう。というわけで、ソートができた。

処理の流れはわかっただろうか。では、計算量を見ていこう。

それぞれのループで何回処理しているかというと…

• 1回目のループで、\(n-1\)回の比較
• 2回目のループで、\(n-2\)回の比較
• …
• n-1回目のループで、\(1\)回の比較

ということから、全部で\(\displaystyle (n-1)+(n-2)+…+1 = \frac{n(n-1)}{2}\)回処理している。

これを計算すると、

\(\displaystyle \frac{n(n-1)}{2} = \frac{n^2}{2} – \frac{n}{2}\)

計算量に直すと、

\(\displaystyle O(\frac{n^2}{2} – \frac{n}{2}) = O(n^2 – n) = O(n^2)\)

つまり、このバブルソートの計算量は\(O(n^2)\)だ。

最後に、安定か不安定か。これは、安定だ。

なぜなら、同じものが二つ並んだ場合、それは入れ替えない。

つまり、同じ数字だった場合の元々の並びは常に維持されているのだ。

選択ソート

これも、先にアルゴリズムとJavaScriptソースコードをお見せしよう。

1. iを0からn-2まで1つずつ増やしながら、以下を繰り返す
   1. arr[i]からarr[n-1]までで最も小さい数を見つけ、その添え字をkとする
   2. arr[i]とarr[k]を入れ替える

function selection_sort(arr){
    var n = arr.length;
    for(var i = 0; i < n - 1; i++){
        var k = i;
        for(var j = i; j < n; j++){
            if(arr[k] > arr[j]){
                k = j;
            }
        }
        var tmp = arr[i];
        arr[i] = arr[k];
        arr[k] = tmp;
    }
}

ある範囲について、一番小さいものを探し(選択)、それをその範囲の先頭と入れ替える。これを繰り返すのだ。だから、選択ソートと呼ぶ。

こちらは直感的に分かりやすいと思う。が、一応上と同じように具体例でも見てみよう。

バブルソートの時と同じ配列[9, 2, 5, 7, 3]を入力したとする。

1回目のループで、全体を見てみよう。一番小さいのは、添え字1の2だ。つまり、k=1となる。

これを、i番目(0番目)、9と入れ替えてあげよう。すると、[2, 9, 5, 7, 3]となる。

そうしたら、バブルソートと同じく先頭の2は並び替え完了だ。そこより後ろの中で、再度同じことをしてあげればいい。

並び替えの様子は以下の表の通りだ。

さあ、次は計算量だ。これはバブルソートと同じ計算になる。

• 1回目のループで、\(n-1\)回の比較
• 2回目のループで、\(n-2\)回の比較
• …
• n-1回目のループで、\(1\)回の比較

というわけで、回数が同じだ。つまり、計算量も\(O(n^2)\)となる。計算過程はバブルソートの方を見て欲しい。

最後に、安定か不安定か。これは、安定ではない。

なぜかというと、例えば以下のような場合。9が2回出てきていて、元の順番で先に出てくるものを赤で、後に出てくるのを青で色付けしてみた。

[9, 3, 9, 2]

これを選択ソートで並び替えてみると…

• 1回目：[2, 3, 9, 9]
• 2回目：[2, 3, 9, 9]
• 3回目：[2, 3, 9, 9]

お分かりだろうか？二つの9が最初と入れ替わってしまっている。

というわけで、これは安定ではないのだ。

挿入ソート

今回の最後。これまでと同じく、アルゴリズムの考え方と具体的なソースを先に。

1. iを1からn-1まで1ずつ増やしながら、以下を繰り返す
   1. i番目の数を、0からi-1番目までの適した箇所までずらす

function insertion_sort(arr){
    var n = arr.length;
    for(var i = 1; i < n; i++){
        for(var j = i; j > 0 && arr[j - 1] > arr[j]; j--){
            var tmp = arr[j];
            arr[j] = arr[j - 1];
            arr[j - 1] = tmp;
        }
    }
}

まず、先頭をすでにソート済みとみなす。

で、その一個次にある数を、その中の適した場所までずらす。つまり、そこに挿入している。

これを、全部に対して行っているのだ。だから、挿入ソート。

これまた上までと同じく、具体例を見ていく。入力配列も、同じ[9, 2, 5, 7, 3]にしよう。

まず、先頭の9だけ整列済みとする。で、その一個次の2を見よう。

2の方が小さいので、9と入れ替える。これで、[2, 9, 5, 7, 3]となる。

もう一つ見てみると、今度は2, 9までが整列済み。そして、その次は5だ。

つまり、整列済みの中に入れてあげると、2, 5, 9が整列できて、残りは7, 3だ。これを繰り返していく。

並べ替えの様子は以下の通り。

これまでと違って、最後までやって整列完了になる。

では、計算量を見てみよう。ちょっと考えてあげる必要がある。

まずは外側のfor文。ここでの計算量は\(O(n)\)だ。

次に、中のfor文。ここは、ものによって異なるが、最悪のパターンを想定すると、1回、2回、…、\(n-1\)回となる。つまり、ここの最悪計算量は\(O(n)\)。

よって、全体で見ると\(O(n * n) = O(n^2)\)だ。

ただ、ベストなパターンを考えると、実は内側の内容は一切行われない。どういうパターンかというと、すでに整列済みの場合。

このときは、計算量が\(O(n)\)まで減ってくれる。つまり、ほとんど整列が済んでいるものに対しては非常に強い。

最後に、安定かどうか。

これは、安定だ。小さいものをずらしていって、同じになったらそれ以上は交換されないので、元の順番が保持されている。

おわりに

今回は、データを並び替えるソートアルゴリズムの中でも、単純なアルゴリズムと呼ばれる三つを紹介した。

計算量、安定かどうかをまとめると以下の通りだ。

これらは、基本的なアルゴリズムの代表格だ。是非、押さえておいて欲しい。

次回は、高速なアルゴリズム…に入りたいのだが、そのための前提知識が必要になる。

これは、考え方(≒アルゴリズム)とデータ構造に分けられる

その中でも、次回は考え方の部分を解説することとしよう。

更新情報はTwitterでも呟いている。よかったらページ下部のTwitterアイコンから覗いていってほしい。

それでは。

オマケ：最悪なソートアルゴリズム

ここからは雑談だ。

最悪なソートアルゴリズム、と書いたのだが、もはやアルゴリズムと呼べるものではない気がする…

名前は、ボゴソートという。アルゴリズムは以下の通り。

1. 入力をランダムに入れ替える。
2. ソート済みか判定する。
   1. ソート済みなら終了
   2. ソート済みでないなら、先頭に戻る

例えるなら、トランプをシャッフルして、ソートされたか確認する。ソートされてないなら、再度シャッフルする。

…平均計算量は\(O(n * n!)\)だそうで、もちろん安定なんかしない。

なお、最悪計算量は\(O(\infty)\)。一生終わらない可能性もある。