挿入ソートはなぜ遅くなる?
挿入ソートは「ほぼ整列済みの配列」には本当に速いです。ただ一つ弱点があります。小さい値が配列の一番後ろにあると、その値が正しい位置(先頭)まで行くのに1マスずつずらしていく必要があります。9マス離れていれば9回、100マスなら100回。遠くにある値ほど損が大きくなります。
例:
[8, 5, 3, 9, 2, 7, 4, 1, 6]では1がほぼ末尾(インデックス7)にあります。挿入ソートだと1が先頭へ行くために隣の要素を七回も押しのける必要があります。
この「1マスずつしか動けない」せいで、挿入ソートはランダムな配列では O(n²) まで遅くなります。
核心アイデア — 「間隔(gap)」を空けて見る
シェルソート(Shell Sort)の発想はシンプルです。最初から隣同士を見るのではなく、離れた要素から先に整理しよう。
- •まず gapマス離れた要素同士だけ をまとめて挿入ソートします。(例: gap=4 ならインデックス 0・4・8 同士、1・5 同士…)
- •次に gap を 半分 に縮めて、より細かく見ます。(4 → 2 → 1)
- •最後の
gap = 1パスは実は ただの挿入ソート です。でもこの頃には配列がほぼ整列済みなので、移動はほとんどありません。
よく使われる間隔列は、配列サイズ n の半分から始めて半分ずつ縮める方式です: n/2 → n/4 → … → 1。
なぜgapを使うと速くなる?
秘密は 「大きなジャンプ」 にあります。
gapが大きいとき、遠く後ろにいた小さい値が 1回の交換で大きな距離をジャンプ します。上の例で 1 は、大きなgapのパスで一気に前方へ大きく移動します。1マスずつ進む挿入ソートとはまったく違います。
だからgapを徐々に縮めて最後の gap = 1 に到達したときには、残りの移動量が大幅に減って います。大きなgapが「大枠」を先に整え、小さなgapが「仕上げ」だけをするわけです。
まとめると、こういう流れです。
1. gap = n/2 から開始する
2. gapマス離れたグループをそれぞれ挿入ソートする
3. gapを半分に縮めて2を繰り返す
4. gap = 1 パスまで終われば整列完了
自分の目で確かめる
gapが 4 → 2 → 1 と縮む間、離れた棒同士が比較(黄)・交換(赤)され、小さい値が大きなジャンプで前方に収まる 全工程 をステップ別の可視化で用意しました。各ステップのgap値と変数の変化まで一目で分かります。
「gapを空けて遠くから整理する」という発想は文章だけだと抽象的ですが、棒が大きなジャンプで動くのを一度見れば、「だから速くなるのか」が一瞬で分かります。