トランプゲームで手札を整理するとき、あなたはどうしているだろうか。
1枚ずつ引いては、すでに並んでいる手札の中の正しい場所に差し込む。「3は1と4のあいだだな」「1が来た、先頭に入れよう」——これを繰り返すと、気づいたときには手札が昇順に並んでいる。この「1枚ずつ差し込む」動作がそのままアルゴリズムになったものが挿入ソートだ。
挿入ソートはバブルソートと同じO(n²)なので「遅いアルゴリズム」に分類される。ただし、「ほぼ整列済みのデータ」に対してだけは驚くほど速い。この特徴を知っておくと、実務でちょうどいい場面で使える。
この記事でわかること
- 挿入ソートの動作をトランプの比喩でステップごとに理解する
- O(n²)になる理由と、最良ケースがO(n)になる条件
- バブルソートとの違いと、挿入ソートが得意な場面
- Pythonでのシンプルな実装コード
1枚ずつ差し込む：動作をステップで追う
📌 要点：未整列部分から1要素を取り出し、整列済み部分の正しい位置に差し込む。これを繰り返すことで全体が整列される。「すでに並んでいる手札に1枚ずつ足していく」イメージ。
配列 [4, 2, 5, 1, 3] を挿入ソートで並び替えてみよう。
最初の状態：
整列済み: [4] 未整列: [2, 5, 1, 3]先頭の4は「1枚だけ」なので、すでに整列済みとして扱う。
ステップ1：2を取り出す
取り出した値: 2
整列済みを右から確認: 4 > 2 → 4を1つ右にずらす
差し込み位置が決まった → [2, 4]
結果: [2, 4, 5, 1, 3]ステップ2：5を取り出す
取り出した値: 5
整列済みを右から確認: 4 < 5 → ここで止まる
差し込み位置が決まった → [2, 4, 5]
結果: [2, 4, 5, 1, 3]ステップ3：1を取り出す
取り出した値: 1
整列済みを右から確認: 5 > 1 → ずらす、4 > 1 → ずらす、2 > 1 → ずらす
先頭まで来た → [1, 2, 4, 5]
結果: [1, 2, 4, 5, 3]ステップ4：3を取り出す
取り出した値: 3
整列済みを右から確認: 5 > 3 → ずらす、4 > 3 → ずらす、2 < 3 → ここで止まる
差し込み位置が決まった → [1, 2, 3, 4, 5]
結果: [1, 2, 3, 4, 5] ✅ 完成| ステップ | 取り出した値 | 整列済み部分 | 配列全体 |
|---|---|---|---|
| 開始 | — | [4] | [4, 2, 5, 1, 3] |
| 1 | 2 | [2, 4] | [2, 4, 5, 1, 3] |
| 2 | 5 | [2, 4, 5] | [2, 4, 5, 1, 3] |
| 3 | 1 | [1, 2, 4, 5] | [1, 2, 4, 5, 3] |
| 4 | 3 | [1, 2, 3, 4, 5] | [1, 2, 3, 4, 5] |
「整列済みの右端から左に向かって比較し、差し込む場所を探す」——これが挿入ソートの本質だ。
Pythonで実装すると
def insertion_sort(arr):
for i in range(1, len(arr)): # インデックス1番目から順番に取り出す
key = arr[i] # 今から差し込む値を手に持つ
j = i - 1 # 整列済み部分の右端から確認を始める
# 差し込む場所が見つかるまで、整列済み部分を右にずらしていく
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j] # 1つ右にずらす（空きを作る）
j -= 1 # 1つ左へ移動して確認を続ける
arr[j + 1] = key # 見つかった場所に差し込む
return arr
# 実行例
cards = [4, 2, 5, 1, 3]
print(insertion_sort(cards)) # → [1, 2, 3, 4, 5]コードの key = arr[i] が「1枚手に持つ」、while ループ内のずらし処理が「場所を空けながら差し込み位置を探す」動作に対応している。
計算量O(n²)とO(n)：トランプの枚数と手間の関係
📌 要点：最悪ケース（完全逆順）はO(n²)。しかし最良ケース（整列済み）はO(n)になる。「1枚取るたびに何枚と比べるか」がケースごとに大きく変わるのが挿入ソートの特徴。
挿入ソートの計算量はケースによって大きく変わる。
| ケース | 計算量 | トランプで言うと |
|---|---|---|
| 最良（整列済み） | O(n) | 1枚取るたびに「右端より大きい」ですぐ確定。比較1回で終わる |
| 平均 | O(n²) | ランダムな並びで、平均して半分くらいの枚数と比べる |
| 最悪（完全逆順） | O(n²) | 1枚取るたびに整列済みの全枚数と比べ続ける |
最悪ケースをイメージすると：
手札が [5, 4, 3, 2, 1]（完全逆順）のとき、
- 4を取る → 5と比較：1回
- 3を取る → 4、5と比較：2回
- 2を取る → 3、4、5と比較：3回
- 1を取る → 2、3、4、5と比較：4回
- 合計：1+2+3+4 = 10回
5枚で10回。n枚では n(n-1)/2 回——これがO(n²)だ。
最良ケースをイメージすると：
手札が [1, 2, 3, 4, 5]（すでに整列済み）のとき、
- 2を取る → 1 < 2 → 即確定：1回
- 3を取る → 2 < 3 → 即確定：1回
- 4を取る → 3 < 4 → 即確定：1回
- 5を取る → 4 < 5 → 即確定：1回
- 合計：4回（=n-1回）
「整列済みのところに持ってくると、1回比べるだけで差し込み場所が確定する」——これがO(n)になる理由だ。
挿入ソートが本領を発揮する場面
📌 要点：「ほぼ整列済み」のデータへの強さが挿入ソートの最大の特徴。新しいデータを1件追加してすぐ再整列するような用途では、バブルソートより大幅に速い。
挿入ソートが他のO(n²)アルゴリズムより優れている場面がある。「ほぼ整列済みのデータ」だ。
たとえば、ほぼ昇順に並んでいる100件のリストに、順序を乱すデータが2〜3件だけ混じっている場合を考えよう。
- バブルソート：100件すべてを対象にn-1パスを実行する。フラグ最適化が効くが、それでも乱れた箇所のあるパスはフルに走る
- 挿入ソート：整列済みの箇所は1回の比較でスキップできる。乱れた2〜3件だけ少し多く比較するだけで済む
挿入ソートが適している具体的な場面：
- 毎日1件ずつデータを追加して再整列する処理
- ほぼ正しい順で並んでいるリストの微調整
- 少量データ（10〜20件程度）のソート
- 他のソートアルゴリズムの「仕上げ処理」として使われる（後述）
情シス部門で、機器の点検記録を日次でCSVに追加していくシステムを扱ったことがある。毎朝1〜2件追加するたびに一覧を日付順に並び直す処理が必要だった。ほぼ整列済みの状態に毎日少数を追加するだけなので、挿入ソートを使うと処理が一瞬で終わる。クイックソートのような重いアルゴリズムを使う必要はなかった。
バブルソートとの違いを整理する
📌 要点：どちらもO(n²)だが「何を比べて何を動かすか」が違う。バブルソートは隣同士を交換し続け、挿入ソートは正しい場所を探してから1回で差し込む。交換回数は挿入ソートのほうが少ない。
| 比較項目 | バブルソート | 挿入ソート |
|---|---|---|
| 動作イメージ | 隣同士がひたすら入れ替わる | 1枚取って正しい場所に差し込む |
| 最悪計算量 | O(n²) | O(n²) |
| 最良計算量 | O(n)（フラグ最適化時） | O(n) |
| 交換（移動）回数 | 多い | 少ない |
| 安定ソート | ✅ | ✅ |
| ほぼ整列済みへの強さ | △（フラグで改善可能） | ◎（構造的に速い） |
| 実装のシンプルさ | ◎ | ○ |
実用上の差は「交換回数が少ない」点にある。バブルソートは隣同士を何度も交換しながら最大値を後ろへ運ぶが、挿入ソートは「差し込む場所が決まってから、まとめてずらして1回で差し込む」。データを書き換える回数が少なく、書き込みコストが高いメモリ（フラッシュメモリ等）では有利になることがある。
実はPythonのTimsortにも使われている
📌 要点：Pythonの組み込みソート（sorted/list.sort）はTimsortというアルゴリズムを使う。TimsortはマージソートとInsertionSortの組み合わせで、小さな部分配列には挿入ソートを使って高速化している。
「挿入ソートは遅いのに、なぜ現役で使われているのか」——答えは実装の仕組みにある。
Pythonの sorted() と list.sort() は Timsort というアルゴリズムを使っている。TimsortはマージソートとInsertionSortを組み合わせた設計で、小さな部分配列（32〜64要素程度）に対しては挿入ソートを使う。
なぜか。少ない要素数ではO(n²)とO(n log n)の差が小さく、挿入ソートのほうがオーバーヘッドが少ない。「速いアルゴリズム」にも準備コストがかかる——それが小さいデータでは挿入ソートに負けることがある、というわけだ。
「使えないアルゴリズム」は実はなく、得意な場面がある。挿入ソートはその代表例だ。
FAQ
- Q挿入ソートの「挿入」とはどういう意味ですか？
- A
「挿入（insertion）」は「差し込む」という意味です。未整列部分から取り出した値を、整列済み部分の正しい位置に差し込む（挿入する）動作に由来します。
トランプで手札を整理するときの「この1枚はここに入れよう」がそのままです。
- Q挿入ソートは安定ソートですか？
- A
はい、安定ソートです。
等しい値の要素は「差し込み時に右端から比較して、等しければそこで止まる」ため、元の順序が維持されます。arr[j] > key（厳密な大なり）を使う限り、等しい値同士は入れ替わりません。
- Qバブルソートと挿入ソート、初心者はどちらから学ぶべきですか？
- A
どちらから始めてもかまいません。バブルソートは「隣同士の交換」という動作が非常にシンプルで視覚的にわかりやすいです。挿入ソートはトランプの手札整理という日常的な比喩があり、動作の意味を理解しやすいという強みがあります。2つをセットで学ぶことで「ソートとは何か」の理解が深まります。
- Q挿入ソートで配列の「ずらし」と「交換」は違いますか？
- A
違います。交換（swap）は2要素を入れ替える操作で、代入が2回必要です。ずらし（shift）は1要素を1つ右に移動する操作で、代入が1回で済みます。挿入ソートは「手に持った値（key）のための空きを作るために右にずらす」ため、交換より代入回数が少なくなります。
- Q挿入ソートと選択ソートの違いは何ですか？
- A
どちらもO(n²)ですが、動作の方向が逆です。挿入ソートは「1枚取って正しい場所を探す（左側の整列済み部分に差し込む）」、選択ソートは「未整列の中から最小値を選んで先頭に置く」動作です。挿入ソートは整列済み部分がどんどん育ち、選択ソートは未整列部分がどんどん縮む、と覚えると区別しやすいです。
- Qどれくらいのデータ量まで挿入ソートを使えますか？
- A
目安は50件以下、または「ほぼ整列済み」なら数百件程度まで実用的です。Pythonの組み込みTimsortも32〜64要素のサブ配列に挿入ソートを使っています。それ以上の件数でランダムなデータには、クイックソートやマージソートを選んでください。
まとめ
- 挿入ソートはトランプを1枚ずつ手に取り、正しい場所に差し込む動作そのもの
- 最悪・平均の計算量はO(n²)。完全逆順のデータが最も遅い
- 最良ケースはO(n)。整列済みデータなら比較が1回ずつで済む
- 「ほぼ整列済み」のデータへの強さがバブルソートより優れている
- Pythonの Timsort は内部で挿入ソートを活用している。「遅い」だけのアルゴリズムではない
手札を整理するとき、あなたはすでに挿入ソートを使っている。「これはここに差し込もう」という判断を毎回繰り返すだけで、最終的にきれいに並ぶ——その単純な動作に、コンピュータサイエンスの美しさが詰まっている。
関連記事
バブルソートと比べながらソートの基礎を固めたい方はこちら。
→ バブルソートとは？エレベーターの入れ替えで理解するO(n²)
「分割して速くする」クイックソートの仕組みへ進む方はこちら。
→ クイックソートとデカルトの分割統治
“`
