挿入ソート

挿入ソートは先頭の整列済み部分へ、次の要素を1つずつ挿入するアルゴリズムです。対象の値を取り出し、それより大きい値を右へずらして空いた位置へ戻します。安定かつ追加空間 O(1) で、最悪時間は O(n²)、整列済みなら O(n) です。

手札を整理するとき、新しいカードより大きいカードを右へずらして間に入れます。挿入ソートも、すでに整列した部分を保ちながら同じ操作を繰り返します。

挿入ソートの仕組み

外側のループは i = 1 から n − 1 まで進みます。arr[0..i − 1] は整列済みで、arr[i] が挿入する値です。まず key = arr[i] として保存します。

j = i − 1 から左へ調べ、arr[j] > key の間は arr[j + 1] = arr[j] で右へずらし、j を1減らします。key 以下の値に出会うか、j が −1 になったら止めます。空いた位置は j + 1 なので、そこへ key を書き込みます。

各走査の開始時に先頭 0..i − 1 が整列済みで、挿入後は 0..i が整列済みになります。この範囲が末尾まで広がると、配列全体が整列します。

挿入ソートのステップ

既定の入力は [38, 12, 56, 7, 41, 23, 19] です。

第1回、i = 1 で key = 12 を保存します。38は12より大きいため右へずらし、j は −1 になります。添字0へ12を入れると、[12, 38, 56, 7, 41, 23, 19] です。

第2回は key = 56。38は56以下なので、ずらさずに終了します。56を元の位置へ戻します。比較は1回、移動は0回です。

第3回は key = 7。56、38、12を順に右へずらし、添字0へ7を入れます。結果は [7, 12, 38, 56, 41, 23, 19] です。

第4回は56だけをずらして41を挿入し、[7, 12, 38, 41, 56, 23, 19]。第5回は56、41、38をずらし、添字2へ23を入れて [7, 12, 23, 38, 41, 56, 19]。第6回は56、41、38、23をずらし、添字2へ19を入れます。完成形は [7, 12, 19, 23, 38, 41, 56] です。

アニメーションでは key が行の上に待機し、j が左へ進みます。要素を右へずらすたびに空き位置が左へ移り、走査後に key がその位置へ入ります。

時間・空間計算量

追加空間は key と添字のための O(1) です。本課は交換を繰り返す形ではなく、key を保存して大きい要素を右へずらす形を使います。

整列済みなら while j >= 0 and arr[j] > key が各走査の最初に不成立となり、要素同士の比較は合計 n − 1 回です。一般には実行時間は Θ(n + I) で、I は入力の転倒数です。各転倒に対応して 1 回ずらします。I = O(n) なら線形時間ですが、「ほぼ整列済み」だけではその条件を保証できません。

この性質から、挿入ソートは小さい配列や整列済み部分を扱う処理に使われます。最悪時は各 key が先頭まで進むため、O(n²) になります。

境界条件

• 空配列・1要素：外側のループを実行しません。
• 整列済み：各走査で最初の比較だけを行い、合計 n − 1 比較です。
• 全要素が同じ：arr[j] > key が成立せず、移動せずに O(n) で終了します。
• 重複値：同じ値に出会うと止まるため、元の相対順序を保ちます。

よくある間違い

• 比較を >= にする：同じ値も右へずらすため、安定性が失われます。
• arr[j] に key を戻す：終了時の j は key 以下の値を指すか、−1です。挿入位置は j + 1 です。
• 保存前に上書きする：key = arr[i] を省くと、最初の移動で挿入対象が消えます。
• ずらす方向を間違える：必要なのは arr[j + 1] = arr[j] です。要素を右へ送り、挿入用の空きを左へ移します。