挿入ソートとは？仕組み・計算量・C++実装例をわかりやすく解説

挿入ソートは、トランプの手札を並べ替えるときの操作によく似た整列アルゴリズムです。カードゲームで手札を昇順に整理する場面を思い浮かべてください。新しいカードを引いたら、すでに並んでいるカードの中から適切な位置を見つけて、そこに差し込みますよね。まさにこれが挿入ソートの基本的な考え方です。

具体的には、データ集合から1つの要素を取り出し（この値を「キー」と呼びます）、そのキーを挿入できる隙間を作るために、左側にあるより大きい要素を順番に右へずらしていきます。そして、正しい位置が見つかったところでキーを挿入します。これを配列の末尾まで繰り返すことで、全体が昇順に整列されていきます。

挿入ソートの計算量

• 時間計算量：最良ケース O(n)、平均ケース・最悪ケース O(n²)
• 空間計算量：O(1)

すでにほぼ整列されたデータに対しては非常に高速に動作する一方、逆順に並んだデータなどでは処理時間が増加します。また、同じ値同士の順序が入れ替わらない「安定なソート」である点も特徴です。

入力と出力

Input:
ソート対象のリスト: 9 45 23 71 80 55
Output:
ソート前の配列: 9 45 23 71 80 55
ソート後の配列: 9 23 45 55 71 80

アルゴリズム

insertionSort(array, size)

入力 − データを格納した配列と、その要素数

出力 − 昇順にソートされた配列

Begin
    for i := 1 to size-1 do
        key := array[i]
        j := i
        while j > 0 AND array[j-1] > key do
            array[j] := array[j-1]
            j := j – 1
        done
        array[j] := key
    done
End

アルゴリズムのポイント

先頭の要素は「整列済み」とみなし、2番目の要素（インデックス1）から順にキーとして取り出します。キーを左側の整列済み領域と比較しながら、キーより大きい要素を1つずつ右へシフトし、シフトが止まった位置にキーを挿入します。こうすることで、左側の領域は常に整列された状態が保たれます。

C++による実装例

#include<iostream>
using namespace std;

void display(int *array, int size) {
    for(int i = 0; i<size; i++)
        cout << array[i] << " ";
    cout << endl;
}

void insertionSort(int *array, int size) {
    int key, j;

    for(int i = 1; i<size; i++) {
        key = array[i];  // 値を取り出す
        j = i;

        while(j > 0 && array[j-1] > key) {
            array[j] = array[j-1];  // 大きい要素を右へずらす
            j--;
        }

        array[j] = key;  // 適切な位置に挿入
    }
}

int main() {
    int n;
    cout << "Enter the number of elements: ";
    cin >> n;
    int arr[n];  // 指定された要素数で配列を作成
    cout << "Enter elements:" << endl;

    for(int i = 0; i<n; i++) {
        cin >> arr[i];
    }

    cout << "Array before Sorting: ";
    display(arr, n);
    insertionSort(arr, n);
    cout << "Array after Sorting: ";
    display(arr, n);
}

実行結果

Enter the number of elements: 6
Enter elements:
9 45 23 71 80 55
Array before Sorting: 9 45 23 71 80 55
Array after Sorting: 9 23 45 55 71 80

ソートの過程（イメージ）

[9] 45 23 71 80 55   ← 先頭は整列済みとみなす
[9 45] 23 71 80 55   ← 45はそのまま挿入
[9 23 45] 71 80 55   ← 23を9と45の間に挿入
[9 23 45 71] 80 55   ← 71はそのまま挿入
[9 23 45 71 80] 55   ← 80はそのまま挿入
[9 23 45 55 71 80]   ← 55を適切な位置に挿入して完成