挿入ソート

Q: 挿入ソートの時間計算量はどれくらいですか？

挿入ソートは平均および最悪の場合で `O(n²)` ですが、すでにソート済みまたはほぼソート済みの配列では `O(n)` です。追加空間は `O(1)` を使います。

Q: 挿入ソートは安定ですか？

はい。挿入ソートはキーより厳密に大きい要素だけをずらすため、等しい要素が互いを追い越すことはなく、相対的な順序が保たれます。

Q: 挿入ソートはいつ使うべきですか？

小さな配列や、すでにほぼソート済みのデータに使いましょう。オーバーヘッドが小さく最良の場合が適応的であるため、Timsort のようなハイブリッドアルゴリズムは小さなランに対して挿入ソートを使います。

Q: 挿入ソートとバブルソートの違いは何ですか？

どちらも `O(n²)` の比較ソートですが、挿入ソートはキーのための空きを作るために要素をずらすのに対し、バブルソートは順序の逆な隣接ペアを繰り返し交換します。挿入ソートは通常、書き込み回数が少なく、実際には特にほぼソート済みのデータで最良の場合 `O(n)` に達するため、性能が優れています。

Q: なぜ挿入ソートは小さな配列でマージソートより速いのですか？

挿入ソートは定数倍のオーバーヘッドが非常に小さく、再帰や追加のメモリ確保がないため、漸近計算量が悪いにもかかわらず、小さな入力では `O(n log n)` のソートを上回ります。まさにこの理由で、Timsort や introsort のようなハイブリッドソートは小さな部分配列に対して挿入ソートに切り替えます。

Q: 挿入ソートは連結リストと配列のどちらで性能が良いですか？

挿入ソートは通常、要素のずらしが主なコストとなる配列向けに書かれます。連結リストではノードを所定の位置につなぎ替えることでずらしを回避できますが、高速なランダムアクセスを失うため、挿入位置を見つけるのに要素ごとに線形時間がかかり、全体のコストは `O(n²)` のままです。

最終更新 2026年7月1日

挿入ソートは、ソート済み配列を1要素ずつ構築します。次の未ソート要素（「キー」）を取り出し、ソート済み領域内でそれより大きいすべての要素を1つ右へずらし、キーをその空いた場所に置きます。これはまさに、多くの人が手札のカードを並べる方法と同じです。上の再生ボタンを押して各キーが挿入される様子を見るか、ずらす操作を1つずつ進めてみてください。

挿入ソートは小さい入力やほぼ整列済みの入力では非常に高速で、データがすでにソート済みの場合は O(n) で動作します。そのため、多くのハイブリッドソートは小さな部分配列に対して挿入ソートに切り替えます。

時間計算量と空間計算量

ケース	計算量	備考
最良の場合	O(n)	すでにソート済み
平均の場合	O(n²)	ランダムな順序
最悪の場合	O(n²)	逆順にソート済み
空間	O(1)	インプレース
安定	はい	等しい要素は相対的な順序を保つ

ステップごとの説明

ステップ	何が起こるか
1	最初の要素をサイズ1のソート済み領域として扱う。
2	次の要素をキーとして取り出す。
3	ソート済み領域でキーより大きい各要素を1つ右へずらす。
4	開いた空きにキーを挿入する。
5	すべての要素が挿入されるまで繰り返す。

具体例

[5, 2, 4, 1] をソートする場合：

パス	配列	操作
開始	`[5, 2, 4, 1]`	`5` はサイズ1の初期ソート済み領域。
1	`[2, 5, 4, 1]`	キー `2`：`5` を右へずらし、`2` を先頭に挿入。
2	`[2, 4, 5, 1]`	キー `4`：`5` を右へずらし、`2` は小さいので停止、`4` を挿入。
3	`[1, 2, 4, 5]`	キー `1`：`5`、`4`、`2` を右へずらし、`1` を先頭に挿入。
完了	`[1, 2, 4, 5]`	すべての要素が挿入され、配列はソート済み。

挿入ソートを使うべき場面

使うべき場合	避けるべき場合
配列が小さい場合（おおよそ `n < 20`）。	配列が大きくランダムな順序の場合。
データがすでにほぼソート済みで、最良の場合 `O(n)` が得られる場合。	保証された最悪の場合 `O(n log n)` が必要な場合。
`O(1)` の追加空間で安定かつインプレースなソートが必要な場合。	多くのずらし操作を行うため、要素の移動コストが高い場合。
データが逐次到着し、オンラインでソート済みを保つ必要がある場合。	入力が逆順にソートされており、最悪の場合 `O(n²)` になる場合。

Insertion Sortのコード

Python, JavaScript, Java, C++, Cによるクリーンで実行可能なInsertion Sortの実装です。言語を選んでコードをコピーするか、Coddyプレイグラウンドに読み込んだ状態で開けます。

PythonでのInsertion SortのコードPython
1def insertion_sort(a):2    for i in range(1, len(a)):3        key = a[i]4        j = i - 15        # Shift larger elements one slot to the right6        while j >= 0 and a[j] > key:7            a[j + 1] = a[j]8            j -= 19        a[j + 1] = key10    return a11
12
13nums = [7, 3, 9, 1, 5, 8, 2]14print("Before:", nums)15insertion_sort(nums)16print("After: ", nums)
このコードをPythonプレイグラウンドで実行

JavaScriptでのInsertion SortのコードJavaScript
1function insertionSort(a) {2    for (let i = 1; i < a.length; i++) {3        const key = a[i];4        let j = i - 1;5        // Shift larger elements right to open a slot for key6        while (j >= 0 && a[j] > key) {7            a[j + 1] = a[j];8            j--;9        }10        a[j + 1] = key;11    }12    return a;13}14
15const data = [5, 2, 9, 1, 7, 3];16console.log("Before:", data);17console.log("Sorted:", insertionSort([...data]));
このコードをJavaScriptプレイグラウンドで実行

JavaでのInsertion SortのコードJava
1import java.util.Arrays;2
3public class Main {4    static void insertionSort(int[] arr) {5        for (int i = 1; i < arr.length; i++) {6            int key = arr[i];7            int j = i - 1;8            // Shift larger elements one slot to the right9            while (j >= 0 && arr[j] > key) {10                arr[j + 1] = arr[j];11                j--;12            }13            arr[j + 1] = key;14        }15    }16
17    public static void main(String[] args) {18        int[] arr = {7, 3, 9, 1, 5, 8, 2};19        System.out.println("Before: " + Arrays.toString(arr));20        insertionSort(arr);21        System.out.println("After:  " + Arrays.toString(arr));22    }23}
このコードをJavaプレイグラウンドで実行

C++でのInsertion SortのコードC++
1#include <iostream>2#include <vector>3
4void printVec(const std::vector<int>& a) {5    for (int x : a) std::cout << x << " ";6    std::cout << "\n";7}8
9void insertionSort(std::vector<int>& a) {10    for (size_t i = 1; i < a.size(); ++i) {11        int key = a[i];12        int j = static_cast<int>(i) - 1;13        // Shift larger elements one slot to the right14        while (j >= 0 && a[j] > key) {15            a[j + 1] = a[j];16            --j;17        }18        a[j + 1] = key;19    }20}21
22int main() {23    std::vector<int> data = {7, 3, 9, 1, 5, 8, 2};24    std::cout << "Before: ";25    printVec(data);26    insertionSort(data);27    std::cout << "After:  ";28    printVec(data);29    return 0;30}
このコードをC++プレイグラウンドで実行

CでのInsertion SortのコードC
1#include <stdio.h>2
3void printArr(const int a[], int n) {4    for (int i = 0; i < n; i++) printf("%d ", a[i]);5    printf("\n");6}7
8void insertionSort(int a[], int n) {9    for (int i = 1; i < n; i++) {10        int key = a[i];11        int j = i - 1;12        // Shift larger elements one slot to the right13        while (j >= 0 && a[j] > key) {14            a[j + 1] = a[j];15            j--;16        }17        a[j + 1] = key;18    }19}20
21int main(void) {22    int data[] = {7, 3, 9, 1, 5, 8, 2};23    int n = sizeof(data) / sizeof(data[0]);24    printf("Before: ");25    printArr(data, n);26    insertionSort(data, n);27    printf("After:  ");28    printArr(data, n);29    return 0;30}
このコードをCプレイグラウンドで実行

挿入ソートのよくある質問

挿入ソートの時間計算量はどれくらいですか？

挿入ソートは平均および最悪の場合で O(n²) ですが、すでにソート済みまたはほぼソート済みの配列では O(n) です。追加空間は O(1) を使います。

挿入ソートは安定ですか？

はい。挿入ソートはキーより厳密に大きい要素だけをずらすため、等しい要素が互いを追い越すことはなく、相対的な順序が保たれます。

挿入ソートはいつ使うべきですか？

小さな配列や、すでにほぼソート済みのデータに使いましょう。オーバーヘッドが小さく最良の場合が適応的であるため、Timsort のようなハイブリッドアルゴリズムは小さなランに対して挿入ソートを使います。

挿入ソートとバブルソートの違いは何ですか？

どちらも O(n²) の比較ソートですが、挿入ソートはキーのための空きを作るために要素をずらすのに対し、バブルソートは順序の逆な隣接ペアを繰り返し交換します。挿入ソートは通常、書き込み回数が少なく、実際には特にほぼソート済みのデータで最良の場合 O(n) に達するため、性能が優れています。

なぜ挿入ソートは小さな配列でマージソートより速いのですか？

挿入ソートは定数倍のオーバーヘッドが非常に小さく、再帰や追加のメモリ確保がないため、漸近計算量が悪いにもかかわらず、小さな入力では O(n log n) のソートを上回ります。まさにこの理由で、Timsort や introsort のようなハイブリッドソートは小さな部分配列に対して挿入ソートに切り替えます。

挿入ソートは連結リストと配列のどちらで性能が良いですか？

挿入ソートは通常、要素のずらしが主なコストとなる配列向けに書かれます。連結リストではノードを所定の位置につなぎ替えることでずらしを回避できますが、高速なランダムアクセスを失うため、挿入位置を見つけるのに要素ごとに線形時間がかかり、全体のコストは O(n²) のままです。