通信用語の基礎知識 IPv4
戻る
全国のICカードこれひとつ

シェルソート

辞書:科学用語の基礎知識 算数・数学編 (NMATH)
読み:シェルソート
外語: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.03 (16-May-2019)
Search System : Copyright © Mirai corporation
Dictionary : Copyright © WDIC Creators club