挿入ソート（Insertion Sort）

1. はじめに

　挿入ソート（Insertion Sort）は、シンプルでありながら効率的なソートアルゴリズムの一つです。日常生活でも、例えばトランプのカードを手札に加えながら順番に並べる時などに、私たちは無意識のうちに挿入ソートの考え方を使っています。この記事では、挿入ソートの基本的な概念、アルゴリズムの動作原理、実装方法、そして他のソートアルゴリズムとの比較について解説します。

2. 挿入ソートとは

　挿入ソートは、配列の要素を一つずつ取り出し、既にソート済みの部分配列の適切な位置に「挿入」していくソートアルゴリズムです。名前の由来もここにあります。

　基本的な考え方は次のとおりです：

1. 配列の最初の要素は、それ自体でソート済みとみなします
2. 未ソートの部分から次の要素を取り出します
3. ソート済みの部分を右から左へ走査し、取り出した要素を適切な位置に挿入します
4. すべての要素が処理されるまで2〜3を繰り返します

3. 挿入ソートの動作例

　例えば、配列 [5, 2, 4, 6, 1, 3] をソートする場合を考えてみましょう。

1. 最初の要素 5 はそれ自体でソート済みとみなします：[5 | 2, 4, 6, 1, 3]
2. 次の要素 2 を取り出し、ソート済み部分と比較して適切な位置に挿入します：[2, 5 | 4, 6, 1, 3]
3. 要素 4 を取り出し、適切な位置に挿入します：[2, 4, 5 | 6, 1, 3]
4. 要素 6 を取り出し、適切な位置に挿入します：[2, 4, 5, 6 | 1, 3]
5. 要素 1 を取り出し、適切な位置に挿入します：[1, 2, 4, 5, 6 | 3]
6. 最後に要素 3 を取り出し、適切な位置に挿入します：[1, 2, 3, 4, 5, 6]

　これで配列は昇順にソートされました。

4. 挿入ソートのシミュレーション

5. アルゴリズムの実装

　挿入ソートの擬似コードは次のようになります：

procedure insertionSort(A: array of items)
   n = length(A)
   for i = 1 to n-1 do
      key = A[i]
      j = i-1
      while j >= 0 and A[j] > key do
         A[j+1] = A[j]
         j = j-1
      end while
      A[j+1] = key
   end for
end procedure

5.1. JavaScript での実装例

function insertionSort(arr) {
  const n = arr.length;
  
  for (let i = 1; i < n; i++) {
    // 現在検討中の要素
    const key = arr[i];
    
    // ソート済み部分の中で、keyより大きい要素を右に移動する
    let j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    
    // 適切な位置にkeyを挿入
    arr[j + 1] = key;
  }
  
  return arr;
}

// 使用例
const array = [5, 2, 4, 6, 1, 3];
console.log(insertionSort(array)); // [1, 2, 3, 4, 5, 6]

5.2. Pythonでの実装例

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        
        # キーより大きい要素を右にシフト
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        
        # 適切な位置にキーを挿入
        arr[j + 1] = key
    
    return arr

# 使用例
array = [5, 2, 4, 6, 1, 3]
print(insertion_sort(array))  # [1, 2, 3, 4, 5, 6]

6. 計算量分析

　挿入ソートの計算量を分析すると：

• 時間計算量：
  • 最良の場合：O(n) – 配列が既にソートされている場合
  • 平均の場合：O(n²)
  • 最悪の場合：O(n²) – 配列が逆順にソートされている場合
• 空間計算量：O(1) – 追加の配列を使用せず、入力配列内で要素を並べ替えるため

7. 挿入ソートの特徴

7.1. 長所

• 単純な実装 – アルゴリズムの概念が理解しやすく、実装も簡単です
• 小さな配列に効率的 – 要素数が少ない場合は、複雑なアルゴリズムよりも速く動作することがあります
• 安定性 – 同じ値の要素の相対的な順序が保持されます
• オンラインアルゴリズム – データが到着する都度処理できます
• 適応的 – ほぼソート済みの配列では効率的に動作します

7.2. 短所

• 大きな配列での非効率性 – 要素数が多い場合、O(n²)の時間計算量は効率的ではありません
• 各要素の挿入に時間がかかる – 特に大きな配列では、要素をシフトする操作がコストになります

8. 他のソートアルゴリズムとの比較

アルゴリズム	最良時間	平均時間	最悪時間	空間	安定性
挿入ソート	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 log n)アルゴリズムよりも優れたパフォーマンスを発揮することがあります。そのため、多くの高度なソートアルゴリズム（クイックソートやマージソートなど）では、小さなサブリストをソートする際に挿入ソートを利用することがあります。

9. 応用例と実用的な使用場面

　挿入ソートは以下のような場面で有用です：

1. ほぼソート済みのデータ – 既にほとんどソートされているデータでは、挿入ソートは高速に動作します
2. 小さなデータセット – 要素数が少ない場合、実装の単純さと低いオーバーヘッドにより効率的です
3. オンラインデータ処理 – データが一つずつ到着する場合、挿入ソートは各要素を到着時に適切な位置に挿入できます
4. 組み込みシステム – メモリが限られている環境では、追加空間を必要としない特性が有利です
5. ハイブリッドソートアルゴリズム – クイックソートやマージソートの一部として小さなサブリストをソートするのに使用されます

10. まとめ

　挿入ソートは、シンプルながらも効果的なソートアルゴリズムです。大規模なデータセットでは効率が低下するものの、小さなデータやほぼソート済みのデータに対しては優れた選択肢となります。また、その単純さと直感的な動作原理は、アルゴリズムの学習を始める人にとって理解しやすいという利点もあります。

　アルゴリズムの選択は常に用途や状況に依存します。挿入ソートの特性を理解し、適切な場面で活用することが重要です。

11. その他のソート