Elegant Access

今日のトピック (Today's Topic)

トピック: Insertion Sort
難易度: beginner
カテゴリー: Sorting Algorithms
時間計算量: O(n^2)
空間計算量: O(1)

概念学習 (Concept Learning)

核心概念

挿入ソート（Insertion Sort） は、最終的にソートされた配列を1つの要素ずつ構築するシンプルで直感的なソートアルゴリズムです。これは、ほとんどの人がトランプカードを手で並べ替える方法と似ています：1枚ずつカードを取り、既にソート済みのカードの中の正しい位置に挿入します。

このアルゴリズムは最初にソート済みの部分配列を維持し、未ソート部分から次の要素を繰り返し取り、必要に応じて要素をシフトしてソート済み部分の正しい位置に挿入します。手の中のカードを1枚ずつ取って、既に持っているカードの中の適切な位置に置くのと同じです。

挿入ソートは、小規模なデータセットやほぼソート済みのデータに対して特に効率的であり、最も実用的なシンプルソートアルゴリズムの1つです。

重要ポイント

安定ソート: 等しい要素の相対順序を維持
インプレース: O(1)の追加メモリ空間のみが必要
適応的: 既に大部分がソート済みのデータに対して効率的（最良ケースO(n)）
オンラインアルゴリズム: データを受信しながらソート可能
シンプルな実装: 理解とコーディングが容易
小規模データセットに効率的: 小さなnに対して高度なアルゴリズムより速いことが多い
ほぼソート済みデータに適している: データがほぼソート済みの場合、優れたパフォーマンスを発揮

アルゴリズムステップ

2番目の要素から開始: 最初の要素は既にソート済みと仮定
キー要素を選択: 次の要素を挿入するキーとして取得
後方に比較: ソート済み部分の要素と右から左へキーを比較
要素をシフト: 大きい要素を1つ右に移動
キーを挿入: ソート済み部分の正しい位置にキーを配置
繰り返し: 配列が完全にソートされるまで、残りのすべての要素に対して続ける

実装 (Implementation)

JavaScript実装

function insertionSort(arr) {
    const n = arr.length;
    
    // 2番目の要素から開始（インデックス1）
    for (let i = 1; i < n; i++) {
        // 挿入される現在の要素
        const key = arr[i];
        let j = i - 1;
        
        // keyより大きい要素を1つ前方に移動
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        
        // keyを正しい位置に挿入
        arr[j + 1] = key;
    }
    
    return arr;
}

// 使用例
const array = [12, 11, 13, 5, 6];
console.log("元の配列:", array);
console.log("ソート後:", insertionSort([...array]));
// 出力: ソート後: [5, 6, 11, 12, 13]

Python実装

def insertion_sort(arr):
    n = len(arr)
    
    for i in range(1, n):
        # 配置される要素
        key = arr[i]
        j = i - 1
        
        # keyより大きいarr[0..i-1]の要素をシフト
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        
        # keyを正しい位置に配置
        arr[j + 1] = key
    
    return arr

# 使用例
array = [12, 11, 13, 5, 6]
print("元の配列:", array)
print("ソート後:", insertion_sort(array.copy()))
# 出力: ソート後: [5, 6, 11, 12, 13]

Java実装

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            
            // keyより大きい要素を1つ前方に移動
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            
            // keyを正しい位置に挿入
            arr[j + 1] = key;
        }
    }
    
    public static void main(String[] args) {
        int[] array = {12, 11, 13, 5, 6};
        System.out.println("元の配列: " + Arrays.toString(array));
        insertionSort(array);
        System.out.println("ソート後: " + Arrays.toString(array));
        // 出力: ソート後: [5, 6, 11, 12, 13]
    }
}

計算量分析

時間計算量：

最良ケース: O(n) - 配列が既にソート済みの場合（比較のみ、シフトなし）
平均ケース: O(n²) - ランダムな順序のデータ
最悪ケース: O(n²) - 配列が逆順にソートされている場合（最大シフト）
比較回数: 入力に応じてn-1からn(n-1)/2の間

空間計算量：

O(1): 変数のための定数量の追加空間のみを使用

特性：

適応的: データの既存の順序を利用
交換回数: 選択ソートより少ないこともあるが、最良ケースより多い

ステップバイステップの例

[12, 11, 13, 5, 6] のソート過程を追跡してみましょう：

初期状態: [12, 11, 13, 5, 6]
          ↑ ソート済み部分

パス1 (i=1, key=11):
  11を12と比較 → 12を右にシフト
  11を挿入: [11, 12, 13, 5, 6]
            ↑↑ ソート済み

パス2 (i=2, key=13):
  13を12と比較 → 13 >= 12、既に正しい位置
  結果: [11, 12, 13, 5, 6]
        ↑↑↑↑ ソート済み

パス3 (i=3, key=5):
  5を13と比較 → 13を右にシフト
  5を12と比較 → 12を右にシフト
  5を11と比較 → 11を右にシフト
  5を挿入: [5, 11, 12, 13, 6]
           ↑↑↑↑↑↑ ソート済み

パス4 (i=4, key=6):
  6を13と比較 → 13を右にシフト
  6を12と比較 → 12を右にシフト
  6を11と比較 → 11を右にシフト
  6を5と比較 → 6 >= 5、停止
  6を挿入: [5, 6, 11, 12, 13]
           ↑↑↑↑↑↑↑↑↑↑ ソート済み

結果: [5, 6, 11, 12, 13]

二分探索最適化

パフォーマンスを向上させるために、二分探索を使用して挿入位置を見つけることができます：

function insertionSortBinary(arr) {
    const n = arr.length;
    
    for (let i = 1; i < n; i++) {
        const key = arr[i];
        
        // 二分探索を使用して挿入位置を見つける
        let left = 0, right = i - 1;
        while (left <= right) {
            const mid = Math.floor((left + right) / 2);
            if (arr[mid] > key) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        // 要素をシフトして挿入
        for (let j = i - 1; j >= left; j--) {
            arr[j + 1] = arr[j];
        }
        arr[left] = key;
    }
    
    return arr;
}

練習問題 (Practice Problems)

問題リスト

Insertion Sort List (LeetCode 147) - リンクリストに挿入ソートを適用
Sort Colors (LeetCode 75) - 計数ソートに挿入ソートの概念を使用
Merge Sorted Array (LeetCode 88) - 類似の挿入ロジック
Insert Interval (LeetCode 57) - 挿入ソートの原理を使用

解法ノート

挿入ソートを使用するとき：

小規模データセット（n < 50）
ほぼソート済みのデータ（最良の選択！）
オンラインソート（データが段階的に到着）
安定したソートが必要
シンプルな実装が必要
ハイブリッドアルゴリズムの一部として使用（例：Timsort、Introsort）

使用すべきでないとき：

ランダムな順序の大規模データセット（クイックソートまたはマージソートを使用）
最悪ケースO(n²)が許容できない場合
データに初期順序がない場合

実世界のアプリケーション：

トランプカードのソート
リアルタイムアプリケーションでソート済みリストの維持
Timsortの一部（Pythonのデフォルトソート）
ハイブリッドソートアルゴリズムの一部
分割統治アルゴリズムの小規模部分配列

重要な詳細 (Important Details)

注意すべきエッジケース

空の配列 [] → 空の配列を返す
単一要素 [1] → 既にソート済み
2つの要素 [2, 1] → 1回の比較とシフト
既にソート済み [1, 2, 3, 4] → O(n)時間（最良ケース！）
逆順にソート済み [5, 4, 3, 2, 1] → O(n²)時間（最悪ケース）
重複要素 [3, 1, 3, 2] → 安定性を維持

利点

✅ 実装と理解がシンプル
✅ 小規模データセットに効率的
✅ 適応的 - ほぼソート済みデータに対してO(n)
✅ 安定したソートアルゴリズム
✅ インプレースソート（O(1)空間）
✅ オンラインアルゴリズム - データ到着時にソート可能
✅ 実践ではバブルソートや選択ソートより優れている
✅ 低オーバーヘッド

欠点

❌ ランダム/逆順ソートデータに対してO(n²)の時間計算量
❌ 大規模データセットには非効率的
❌ 遠い要素に対して多くのシフトが必要
❌ アクセスが遅いメディアに保存されたデータには不適

他のソートとの比較

アルゴリズム	時間（最良）	時間（平均）	時間（最悪）	空間	安定性	適応性
挿入ソート	O(n)	O(n²)	O(n²)	O(1)	✅	✅
選択ソート	O(n²)	O(n²)	O(n²)	O(1)	❌	❌
バブルソート	O(n)	O(n²)	O(n²)	O(1)	✅	✅
クイックソート	O(n log n)	O(n log n)	O(n²)	O(log n)	❌	❌
マージソート	O(n log n)	O(n log n)	O(n log n)	O(n)	✅	❌
ヒープソート	O(n log n)	O(n log n)	O(n log n)	O(1)	❌	❌

挿入ソートが特別な理由

ほぼソート済みデータに最適: データがほぼソート済みの場合、挿入ソートはほぼO(n)時間で実行
オンラインアルゴリズム: データを受信しながらソート可能
ハイブリッドアルゴリズムで使用: 多くの高度なアルゴリズムが小規模部分配列に挿入ソートを使用
実践的パフォーマンス: 最悪ケースO(n²)にもかかわらず、低オーバーヘッドのため小規模配列ではマージソートより速いことが多い

今日の振り返り (Daily Reflection)

関連アルゴリズム:

バブルソート: 同様のO(n²)計算量だが実践では効率が低い
選択ソート: 同じ計算量だが適応的ではない
シェルソート: より優れたパフォーマンスを持つ挿入ソートの高度バージョン
マージソート: 大規模データセットに適しているが、小さなnでは挿入ソートが勝つ
Timsort: 小規模ランに挿入ソートを使用するハイブリッドアルゴリズム
二分挿入ソート: 二分探索を使用して挿入位置を見つける

アルゴリズム日記

アルゴリズム日記 - Insertion Sort