1 歩ずつ動かす
[5, 2, 8, 1, 9, 3, 7, 4] を小さい順に並べる
- 50
- 21
- 82
- 13
- 94
- 35
- 76
- 47
- 取り出した値 (上の箱)
- 比較中
- 移した
- 入れた
- 空き
- 並び済みの範囲
- 箱の下の数字は添字
1 歩目 / 全 47 歩比べた回数 0 回ずらした回数 0 回
8 個の値を小さい順に並べます。左端の 1 個だけなら、もう並んでいると見なします。
いま動いている疑似コードの行
- 1i を 1 から n - 1 まで 1 つずつ増やす
- 2key = a[i] (取り出す)
- 3j = i - 1
- 4j >= 0 かつ a[j] > key のあいだ繰り返す
- 5a[j + 1] = a[j] (右へずらす)
- 6j = j - 1
- 7a[j + 1] = key (空きに入れる)
見本を変える
予想してみる
いまは 1 歩目です。
次に比べるのは、どの添字でしょう。
今回わかること
- 値を 1 つ取り出し、左の並び済みへ差し込む流れ
- 比べる回数とずらす回数が、入力の並び方で大きく変わる理由
前提
- 配列と添字 (0 から数える番号)
- for 文と while 文
- 2 つの値の大小を比べる書き方
どんな並べ方か
挿入ソートは、左から順に値を 1 つずつ取り出し、すでに並んでいる左側の正しい位置へ差し込んでいく並べ方です。
手札のトランプを 1 枚ずつ並べ直すときと同じ動きです。ほとんど並んでいる配列なら、すぐに終わります。
手順と具体例
- 1左端の 1 個は、それだけで並んでいると見なす
- 2次の値を取り出し、その場所を空きにする
- 3空きの左隣と比べ、左隣のほうが大きければ空きへずらす
- 4左隣が取り出した値以下になるか左端に着いたら、空きに入れる
- 5右端の値まで、取り出しと差し込みを繰り返す
| 取り出した値 | 比べた / ずらした | 並び済み |
|---|---|---|
| 2添字 0 へ | 1 回 / 1 回 | 2, 5 |
| 8添字 2 へ | 1 回 / 0 回 | 2, 5, 8 |
| 1添字 0 へ | 3 回 / 3 回 | 1, 2, 5, 8 |
| 9添字 4 へ | 1 回 / 0 回 | 1, 2, 5, 8, 9 |
| 3添字 2 へ | 4 回 / 3 回 | 1, 2, 3, 5, 8, 9 |
| 7添字 4 へ | 3 回 / 2 回 | 1, 2, 3, 5, 7, 8, 9 |
| 4添字 3 へ | 5 回 / 4 回 | 1, 2, 3, 4, 5, 7, 8, 9 |
比べる回数と計算量
| 場合 | 比べる回数 | 計算量 |
|---|---|---|
| いちばん速い | n - 1 回 (もう並んでいる) | O(n) |
| 平均 | およそ n² ÷ 4 回 | O(n²) |
| いちばん遅い | n(n - 1) ÷ 2 回 (逆順) | O(n²) |
8 個の逆順なら 28 回比べて 28 回ずらします。もう並んでいれば 7 回比べるだけで、1 回もずらしません。
使いどころ
向いているとき
- 要素が数十個までの、小さい配列のとき
- ほとんど並んでいる配列に、少しだけ値を足したとき
- 同じ値の順番を崩したくないとき (安定な並べ方)
向いていないとき
- 要素が数千個を超える大きい配列 (マージソートやクイックソートを使う)
- 逆順に近い配列 (ずらす回数がいちばん多くなる)
コード
疑似コード
- 1i を 1 から n - 1 まで 1 つずつ増やす
- 2key = a[i] (取り出す)
- 3j = i - 1
- 4j >= 0 かつ a[j] > key のあいだ繰り返す
- 5a[j + 1] = a[j] (右へずらす)
- 6j = j - 1
- 7a[j + 1] = key (空きに入れる)
実際のコード
python実行可能
出力
▶ 実行ボタンを押すと結果がここに表示されます
Python と JavaScript は、書き換えて「実行」を押すと、その場で結果が出ます。Java は読むだけの欄です。
よくある疑問
- a[j] > key を a[j] >= key にすると、何が変わりますか？
- 同じ値も右へずらすので、同じ値どうしの順番が入れ替わります。並びの結果は同じでも、安定な並べ方ではなくなります。
- Python の sorted や JavaScript の sort と比べて、どちらが速いですか？
- 大きい配列では言語の組み込みの並べ替えのほうがずっと速いです。ただ、組み込みの並べ替えも、短い区間では中で挿入ソートを使うことがあります。
- 取り出した値を、なぜ配列の外に持つのですか？
- 右へずらすと、取り出した場所が上書きされるからです。先に key へ写しておくので、ずらしたあとでも空きに入れ直せます。
