シェルソート
読み：シェルソート
外語：Shell's sort
挿入ソートの改良版。数列を一定間隔で分割して挿入ソートを行なう。次第に間隔を狭めていき、最後に通常の挿入ソートを行なう。これによりデータの移動量が少なくなるためソートが高速化される。
最悪計算量はO(n^2)であるが、数列の分割方法によってはO(n^1.25)程度の計算量になる。
なお、シェルソートのShellは貝殻ではなく、考案者の名前D.L.Shellに由来する。
シェルソートの手順
45 21 98 36 5 78 23 27 90 初期状態
---------------------------------------------------------------
45 36 23 数列を分割する
21 5 27
98 78 90
---------------------------------------------------------------
23 36 45 分割した数列ごとに挿入ソートを行なう
5 21 27
78 90 98
---------------------------------------------------------------
23 78 21 45 98 間隔を狭めて再び分割する
5 36 90 27
---------------------------------------------------------------
21 23 45 78 98 分割した数列ごとに挿入ソートを行なう
5 27 36 90
---------------------------------------------------------------
5 21 23 27 36 45 78 90 98 通常の挿入ソートを行なう(終わり)
再検索