手札を整えるように各要素を整列済み区間へ挿入するソートを棒アニメーションで確認。ほぼ整列済みデータでO(n)に近い理由が分かります。
アルゴリズム
配列
比較
0
交換/書込
0
ステップ
0/1,373
読み
0
補助メモリ
0
再帰の深さ
1/1
速度を落として「1ステップ」で疑似コードのハイライトと棒の色を見比べてみてください。
疑似コード
for i ← 1 to n−1
key ← a[i], j ← i−1
while j ≥ 0 and a[j] > key
a[j+1] ← a[j], j ← j−1
a[j+1] ← key
計算量
| 最良 | O(n) |
|---|---|
| 平均 | O(n²) |
| 最悪 | O(n²) |
| 空間 | O(1) |
| 安定 | ○ |
挿入ソートは2番目の要素から1つずつ取り出し(key)、左の整列済み区間で自分より大きい値を後ろへずらして空いた場所へ挿入します — トランプの手札整理と同じ動きです。
最悪はO(n²)ですが、ほぼ整列済みなら各要素の移動が少なく実質O(n)に近づきます。Timsort等のハイブリッドソートが短い区間で挿入ソートに切り替える理由です。安定・インプレースソートです。 ソート可視化