シェルソート

挿入ソートの改良版。数列を一定間隔で分割して挿入ソートを行なう。次第に間隔を狭めていき、最後に通常の挿入ソートを行なう。これによりデータの移動量が少なくなるためソートが高速化される。

最悪計算量は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 通常の挿入ソートを行なう(終わり)

通信用語の基礎知識検索システム WDIC Explorer Version 7.04a (27-May-2022)