Rubyで学ぶ挿入ソート：仕組みから計算量まで徹底解説

※本記事は、Rubyでさまざまなソートアルゴリズムを実装するシリーズの第4回です。第1回ではバブルソート、第2回では選択ソート、第3回ではマージソートを取り上げました。

データのソート手法をさまざまな角度から探っていくシリーズもいよいよ折り返し地点。今回は挿入ソート（Insertion Sort）に焦点を当てます。挿入ソートには魅力的な特徴がたくさんあります。

まず、挿入ソートは安定（stable）なアルゴリズムです。つまり、同じキーを持つ要素同士の相対的な順序が入れ替わることがありません。また、インプレース（in-place）アルゴリズムでもあるため、ソート結果を保存するための新しい配列を作成する必要がありません。さらに、これから見ていくように、実装がとてもシンプルなのも大きな魅力です。

なぜ挿入ソートを学ぶべきなのか

繰り返しになってしまうのは承知の上ですが、これまでの記事でも述べてきたように、データをソートするためのさまざまな手法と、それぞれのトレードオフを理解しておくことは非常に重要です。

たとえば、挿入ソートは大規模なデータセットにはあまり向いていません（詳細は後述します）。しかし、小規模なデータセットや、すでにほぼソート済みのデータに対しては、十分に実用的かつ高い効率を発揮します。その理由は、実装を追っていくうちに自然と理解できるはずです。

もちろん、実務では各プログラミング言語が提供する組み込みのソートメソッドを使うことがほとんどでしょう。それでも、ペアプログラミング形式の面接課題や、計算量（タイムコンプレキシティ）に関する質問として、挿入ソートがテーマになることは珍しくありません。この記事を読み終える頃には、挿入ソートのコードを自力で書けるだけでなく、その時間計算量についても自信を持って説明できるようになっているはずです。

視覚的にイメージをつかもう

コーディングに入る前に、ぜひ以下の動画をご覧ください。「ダンス」で挿入ソートの動きを表現したもので、個人的には何度見ても飽きない傑作です :)

コードをステップごとに解説

それでは、実際のコードを見ていきましょう。

def insertion_sort(array)
    for i in 1...(array.length)  # ステップ1
        j = i # ステップ2
        while j > 0 # ステップ3
            if array[j-1] > array[j] # ステップ4
                temp = array[j]
                array[j] = array[j-1]
                array[j-1] = temp
            else
                break
            end
            j = j - 1 # ステップ5
        end
    end
    return array
end

ステップ1：外側のforループ

まず、変数 i を 1 に設定し、配列の長さに達するまで増加させ続ける for ループから始めます。先頭要素だけでは比較対象がないため、開始位置が 1 になっている点に注目してください。

ステップ2：変数jの初期化

続いて、別の変数 j を作成し、現在の i の値で初期化します。

ステップ3：内側のwhileループ

次に、j が 0 より大きい間だけ継続する、ネストされた while ループが登場します。j は 1 から始まるため、少なくとも1回は必ず実行されることがわかります。

ステップ4：比較とスワップの判定

if...else ブロックは一見とっつきにくく感じるかもしれませんが、順を追えば決して難しくありません（迷ったら、いつでもダンス動画に戻りましょう！）。

if の条件では、array[j-1] が array[j] より大きいかどうかを判定します。j が現在 1 であれば、実質的には array[0] と array[1]、つまり配列の先頭2要素を比較していることになります。

前の要素（array[0]）の方が大きければ、当然スワップが必要です。それが if ブロック内で行われる処理です。逆に、前の要素の方が小さければ、その部分はすでに整列済みということなので、else ブロックの break で内側のループを抜けます。

ステップ5：jを減らして左方向へ展開

最後に j をデクリメントします。こうして for ループに戻ると、今度は i が 2 になります。j が 1 ではなく 2 からスタートするため、array[1] と array[2] の比較から始まり、条件が満たされる限り while ループを複数回通るイメージです。これこそが「挿入」という名前の由来——整列済み領域の適切な位置へ要素を挿入していく動きです。

実際のデータで動きを追ってみる

理解を深めるため、次のサンプル配列を使ってコードの動きを具体的に追ってみましょう。

[5, 7, 2, 10, 9, 12]

1回目： 5 と 7 を比較します。5 < 7 なので、即座に break して次へ進みます。

2回目： 7 と 2 を比較します。今度はスワップが必要なので [5, 2, 7, 10, 9, 12] となり、さらに 2 を 5 とスワップして [2, 5, 7, 10, 9, 12] に到達します。

3回目： 10 と 7 を比較します。すでに正しい順序なので、そのまま通過です。

4回目： 10 と 9 を比較するとスワップが必要。その後 7 は 9 より小さいため、追加のスワップは発生せず、[2, 5, 7, 9, 10, 12] となります。

5回目： 最後の 12 は 10 より大きいため、そのまま完了。無事ソートできました！

パフォーマンス分析：計算量を理解する

これまで取り上げてきたソートアルゴリズムの中には、バブルソートのように実務でほとんど使われないものもあります。しかし、挿入ソートは状況によっては十分に現実的な選択肢になり得ます。

配列がすでにソート済みであれば、挿入ソートは非常に高速かつ効率的に動作します。一方で、逆順の配列をソートする場合はどうなるでしょうか。これは挿入ソートにとって悪夢のようなシナリオです。

• 最良ケース：O(n) — 配列がすでにソート済みの場合、ループを n 回通るだけで済みます。検証したい場合は、メソッドの先頭に puts i を追加し、ソート済み配列を渡して実行してみてください。
• 最悪ケース：O(n²) — 配列が逆順の場合、連続的なスワップが必要になり、すべての要素で if 条件にヒットします。こちらも、逆順の配列を渡してカウンター変数を出力すれば、実際に確認できます。

最悪ケースが O(n²) という点はバブルソートや選択ソートと共通していますが、それでも一般的には挿入ソートの方が好まれます。その理由は主に2つあります。

1. 挿入ソートの最良ケースは O(n) であるのに対し、選択ソートの最良ケースは O(n²) のままです。
2. 挿入ソートはバブルソートよりもスワップ回数が少なくて済みます。

まとめ

本記事を通じて、挿入ソートの長所と短所、そしてアルゴリズムの内部動作についてしっかり理解を深められたなら幸いです。さらに学びたい方は、Wikipediaの「挿入ソート」のページもあわせてチェックしてみてください。次回のシリーズ記事もお楽しみに！