概要
概要
新しい要素を 1 つ取り出し、左側の整列済み領域の適切な位置へ挿入します。ほぼ整列済みの入力では強いアルゴリズムです。
ソート / Insertion Sort（挿入ソート）
新しい要素を 1 つ取り出し、左側の整列済み領域の適切な位置へ挿入します。ほぼ整列済みの入力では強いアルゴリズムです。
目次
このページでわかること
概要
新しい要素を 1 つ取り出し、左側の整列済み領域の適切な位置へ挿入します。ほぼ整列済みの入力では強いアルゴリズムです。
考え方
for i = 1 to n - 1
key = a[i]
while j >= 0 and a[j] > key
a[j + 1] = a[j]
a[j + 1] = key要点
O(n)
O(n²)
O(n²)
はい
補足
すでにほぼ整列済みなら、左へ大きく動く要素が少ないため速くなります。
カードを手札に差し込む動きに近いです。
交換を連発するより、ずらして最後に挿入する発想です。
動きで確認
ここでは「取り出した key を追う」を見ながら、上で読んだ内容を動きと結びつけます。
次に見る
比較すると違いがわかりやすいページを先に置いています。