挿入ソート｜コードで実践

挿入ソート

このレッスンで分かること

「比較しながら右シフトし、ちょうど良い場所で key を置く」 — これが挿入ソートの本質

計算量は最悪 O(n^2) ですが、ほぼ整列済みの配列なら O(n) にまで縮みます

挿入ソート (insertion sort) は、トランプを左手で並べていく動きをそのままコードにしたソートです

挿入ソートとは

トランプを並べるように、要素を 1 つずつ既に整列済みの部分に差し込む挿入ソートを実装する。本レッスンでは、挿入ソートの基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。

挿入ソート (insertion sort) は、トランプを左手で並べていく動きをそのままコードにしたソートです。「左側はすでに整列済み」と決めておき、右から 1 枚ずつカードを取って、左の中で 正しい位置に差し込む ことを繰り返します。

計算量は最悪 O(n^2) ですが、ほぼ整列済みの配列なら O(n) にまで縮みます。これは選択ソートにはない特性です。実は内部的に挿入ソートをハイブリッドで使っているライブラリも多く、Timsort (Python の sorted、Java の Arrays.sort) も小さな配列では挿入ソートに切り替えています。

挿入ソートは「整列済み領域に 1 つずつ正しい位置で差し込む」。安定で、ほぼ整列済みなら高速。

アルゴリズムの動き

[5, 2, 4, 6, 1, 3] をソートする例を追います。

i = 1: key = 2。左の 5 より小さいので、5 を右にずらして [2, 5, 4, 6, 1, 3] に。
i = 2: key = 4。5 を右にずらして [2, 4, 5, 6, 1, 3]。
i = 3: key = 6。5 より大きいのでそのまま。
i = 4: key = 1。6, 5, 4, 2 を全部右にずらして [1, 2, 4, 5, 6, 3]。
i = 5: key = 3。6, 5, 4 を右にずらして [1, 2, 3, 4, 5, 6]。

各ステップで「key 以下の値が出てくる位置」まで左の要素を右シフトしているのがポイントです。

diagram (will load when visible)

図のポイント (テキスト併記)

「比較しながら右シフトし、ちょうど良い場所で key を置く」 — これが挿入ソートの本質

「比較しながら右シフトし、ちょうど良い場所で key を置く」 — これが挿入ソートの本質。

Python での実装

Python

def insertionSort(arr):
    a = list(arr)
    n = len(a)
    for i in range(1, n):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
    return a

a[j + 1] = a[j] で 1 つずつ右に押し出し、j がマイナスになるか a[j] <= key になったところに key を置きます。

JavaScript での実装

JavaScript

function insertionSort(arr) {
  const a = [...arr];
  const n = a.length;
  for (let i = 1; i < n; i++) {
    const key = a[i];
    let j = i - 1;
    while (j >= 0 && a[j] > key) {
      a[j + 1] = a[j];
      j--;
    }
    a[j + 1] = key;
  }
  return a;
}

バブル / 選択との関係

ソート	比較	書き込み	早期終了	安定
バブル	`O(n^2)`	`O(n^2)`	フラグで可能	安定
選択	`O(n^2)`	`O(n)`	不可	不安定
挿入	`O(n^2)` 最悪 / `O(n)` 最良	`O(n^2)` 最悪	自然と早く終わる	安定

ソートの中で「すでに整列済みに近い」入力が来るなら挿入ソートが最速。逆に完全な逆順なら最悪ケース。

よくある間違い

1 つ目は 内側ループの範囲外チェック忘れ。j >= 0 を抜くと a[-1] で予期せぬ要素にアクセスしたり (Python は末尾要素を参照) 例外になります。2 つ目は key の保存忘れ。a[i] を毎回参照するとシフト中に上書きされてしまうので、最初に key 変数へコピーします。3 つ目は 比較の向き。> ではなく >= にすると 安定性が崩れます (同じ値の順序が逆転)。

やってみよう

[5, 4, 3, 2, 1] (最悪ケース) と [1, 2, 3, 4, 5] (最良ケース) で内側ループの実行回数を数えてみる。
比較を二分探索に置き換える バイナリ挿入ソート を考えてみる (シフト回数は同じだが比較回数は O(n log n))。
連結リストで挿入ソートを書くと、シフトが消えて挿入が O(1) になる。次のレッスンで考えてみる。

Timsort と挿入ソート

Python の sorted や Java の Arrays.sort (オブジェクト版) で使われている Timsort は、実は 挿入ソートとマージソートのハイブリッド です。32 要素未満の小さな部分配列では挿入ソートに切り替えることで、関数呼び出しオーバーヘッドと最良時 O(n) を活かしています。

もう 1 つの工夫は run の検出。入力の中に「すでにソート済みの連続部分 (run)」があれば、それを 1 つの整列済み単位として扱い、マージで結合します。実世界のデータは完全ランダムではなく、部分的に整列している ことが多いため、Timsort はその性質を最大限に活かす設計になっています。

Timsort は「現実のデータはほぼ整列済みであることが多い」という観察から生まれた、実用最強クラスのソート。

計算量の証明スケッチ

挿入ソートの平均計算量は、ランダム順序の配列で 逆転対 (前にあるべきものが後ろに来ているペア) の数 I に比例します。ランダム配列で I の期待値は n(n-1)/4、すなわち O(n^2)。一方、I = 0 (整列済み) のときは内側ループが回らず O(n) です。これが「ほぼ整列済みで速い」理由の数学的根拠。

よくある質問

Q. このトピックは実務でどう役立ちますか？

A. DB のクエリ最適化、API 設計、データ構造の選択など、設計判断の根拠になります。表面的にライブラリを使うだけでなく「なぜそれが速いのか」を理解できると、性能問題を未然に防げます。コーディング面接でも頻出のテーマです。

Q. 計算量はどう求めれば良いですか？

A. ループのネストごとに掛け算する、再帰なら漸化式から解く、というのが基本です。Big-O 表記は定数倍と低次の項を無視するため、n の指数（n²、n log n など）に注目してください。最悪・平均・最良の 3 つを意識すると説得力が増します。

Q. 覚えるべき定番アルゴリズムは何ですか？

A. 二分探索、クイックソート/マージソート、BFS/DFS、ダイクストラ、DP の基本問題（フィボナッチ・ナップサック）が必修です。これらを「白紙から書ける」状態にすると、応用問題が一気に解けるようになります。

次のレッスン

次は マージソート で、トランプを並べるように、要素を 1 つずつ既に整列済みの部分に差し込む挿入ソートを実装するを学びます。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

挿入ソートの要点を自分の言葉で説明できる
このレッスンの最小コード (または操作手順) を見ずに書ける
練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. 挿入ソートとは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン

挿入ソート