シェルソート

読み:シェルソート
外語:Shell's sort 英語 , Shell 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 通常の挿入ソートを行なう(終わり)
関連する用語
ソート
単純挿入ソート
コムソート

コメントなどを投稿するフォームは、日本語対応時のみ表示されます


KisoDic通信用語の基礎知識検索システム WDIC Explorer Version 7.04a (27-May-2022)
Search System : Copyright © Mirai corporation
Dictionary : Copyright © WDIC Creators club