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

前々回はバブルソート、前回は選択ソートを解説してきた。

今回は、残る一つの挿入ソートについて解説していこう。

これも、考え方は比較的単純だ。

一個一個、データの動きに着目しながら理解を深めていってほしい。

シノ

今回で単純なソートアルゴリズムは最後、
ゆっくりでいいから確実に理解しよう！

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

挿入、という名前通りの動きとなる。

次に揃えるデータを適した箇所へ挿入し、後ろのデータを一個ずつずらしていく、というのが基本的な動きだ。

これを繰り返して、全体をソートしていく。

これも、先にアルゴリズムを出してしまおう。

入力は恒例のn個の配列data。

出力も、ソート済みのdata配列だ。

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

では、具体的な動きを見ていこう。

入力するデータは、今までと同じ以下の配列としておこう。

さて、いきなりだが、先頭の5はソート済みとみなす。

そして、最初は一個後ろの3を、適した場所までずらしていく。

今回、5の前なので、3は0番目に、5は一個ずれて1番目になる。

次に見るのは、2番目の4。

これは、5の部分に入ればちょうどいいので、1番目になる。

その5はさらに一個ずれて、2番目へ。

このように、範囲を広げながら、広げたときに入ってきた数を適した場所に挿入していくのが、挿入ソートになる。

以降、最後まで続けてみよう。

これで、ソートが完了になる。

他と違うのは、最後の一個もしっかりソートしなければいけないこと。

例えば、ここに0があったら、一番先頭まで来なければいけないので、そこだけ注意しよう。

この挿入ソートは、安定なソートだ。

同じだったら入れ替えないようにすればいいので、元の順番を保持できる。

挿入ソートの計算量

次に、計算量を見ていこう。

まず、外側のfor文でn回。

内側は、最悪の場合で見ると、1回、2回、…、n-1回となっているので、計算量的にはn回となる。

よって、全体は\(O(n \times n) = O(n^2)\)だ。

そう、単純なソートアルゴリズムは、全て計算量が\(O(n^2)\)となる。

数が少なければいいが、データ数が増えると時間がかかってしまうので、高速なアルゴリズムの検討もしてみよう。

挿入ソートのサンプルプログラム

最後、参考までに挿入ソートのサンプルプログラムを。

言語はこれまたJavaScriptだ。

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

おわりに

今回は、挿入ソートについて解説した。

これで、単純なソートアルゴリズムと呼ばれる三つのアルゴリズムの解説が済んだ。

次回以降は、高速なアルゴリズムとなる。

考え方が複雑になってくるので、一個一個落ち着いて進めていこう。