挿入ソート
左側に並べ終えた部分を作り、値を1つずつ加えていきます。新しい値は取り出され、より小さい値に当たるまで左へ動きます。
- Ω(n)
- Θ(n²)
- O(n²)
- O(1)
- はい
- はい
最良: この方法にとって一番楽な入力のとき、リストのサイズ n に応じて時間がどう増えるか。
平均: ふつうの場合に、n に応じて時間がどう増えるか。n² なら値の数が2倍で時間は約4倍。n log n はずっとゆっくり増えます。
最悪: 一番難しい入力での増え方。速さが決して落ちてはいけないときに役立ちます。
メモリ: リストのほかに必要な追加メモリの量。1 なら変数がいくつかだけ、n ならリストのコピー1つ分です。
安定: 同じ値どうしが元の順番を保ちます。レコードを1つの項目で並べ替えるときに大切です。
追加メモリ不要: 2つ目のリストを使わず、リストそのものの中で並べ替えます。
- 比較中
- 移動中
- 取り出した値
- 並べ終えた部分
- 位置が確定
試してみましょう: ほぼ並んでいるリストを選んでください。ほとんど何もずらさないので、ごく少ないステップで終わります。
仕組み
左側の並べ終えた部分は、いつも順番どおりです。次の値を取り出し、その部分でそれより大きい値をすべて1つ右へずらします。空いた場所に値を入れます。トランプの手札を並べるときと同じやり方です。
向いている場面
短いリストや、ほぼ並んでいるリストに向いています。そういうリストではとても速いからです。実際の並べ替えライブラリも、速い方法の中で小さく分けた部分にはこれを使います。