シェルソート
読み：シェルソート
外語：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 通常の挿入ソートを行なう(終わり)

再検索