挿入ソート

途中まで並んでいるのに、また最初から比べている

選択ソートは、入力が [1, 2, 3, 4, 5] のようにすでに並んでいても、毎回すべての要素を見て最小値を探します。手間が入力の状態にまったく左右されません。せっかく並んでいるという情報を、使わずに捨てています。

トランプを配られたときのことを思い出してください。左手の中はすでに並んでいて、新しい 1 枚を正しい隙間に差し込むだけです。すでに並んでいる部分をもう一度見比べたりしません。この動きをそのまま写したのが挿入ソートです。

差し込むには、まず 1 枚を手に取る

配列の上で差し込みを実現するには、場所を空ける必要があります。やり方は、差し込みたい値を先に取り出して変数に持ち、空いたマスへ左の値を 1 つずつ落としていくことです。

入れ替えを 3 回やると書き込みは 9 回ですが、この形なら 4 回で済みます。比べているのは常に「手に持っている値」と「左隣の値」の 2 つだけで、左隣のほうが大きい間は落とし続け、そうでなくなったところが置き場所です。

左から順に、手札を 1 枚ずつ増やす

[5, 2, 4, 6, 1, 3] を追います。縦線の左が並び終わった部分です。

• 5 | 2 4 6 1 3 — 2 を取る。5 を右へ落として 2 5 | 4 6 1 3
• 4 を取る。5 を落として 2 4 5 | 6 1 3
• 6 を取る。左隣の 5 のほうが小さいので、そこで即決 2 4 5 6 | 1 3
• 1 を取る。6, 5, 4, 2 をすべて落として 1 2 4 5 6 | 3
• 3 を取る。6, 5, 4 を落として 1 2 3 4 5 6

最初の 1 個は、それだけで「並び終わった部分」として成立しているので、手を付けるのは 2 個目からです。

ここで、6 を取ったときの動きに注目してください。比較 1 回で終わっています。[1, 2, 3, 4, 5] を入れると全部の回がこれになり、落とす作業が一度も起きません。逆順の [5, 4, 3, 2, 1] は毎回すべてを落とすので最悪になります。つまり挿入ソートの手間は、入力がどれくらい並んでいるかで決まります。ログの追記やスコアの更新のように「ほぼ並んでいるところへ数件だけ割り込む」データとは、非常に相性がよい性質です。

よくある間違い

key に取り出さずに、差し込みたい値を a[i] のまま参照し続けることです。左の値を右へ落とした瞬間に a[i] が上書きされ、差し込むはずだった値が消えます。落とし始める前に、必ず手に取ってください。

1. 組み込みのソート関数 (Python の sorted, JS の sort, Go の sort.Slice) は使わない
2. 整列済み領域に key を差し込む挿入ソートで実装する
3. 戻り値は新しい配列で、入力 arr を破壊的に書き換えない