シェルソート

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索
シェルソート
Step-by-step visualisation of Shellsort
間隔 23, 10, 4, 1 でのシェルソートの実行
クラス ソート
データ構造 配列
最悪計算時間 O(n2)
最良計算時間 O(n log2 n)[1]
平均計算時間 使用する間隔列に依存
最悪空間計算量 О(n) total, O(1) auxiliary
シェルソートアルゴリズムは、カラーバー

シェルソート改良挿入ソート英語: Shellsort, Shell sort, Shell's method)は、in-placeな比較ソートアルゴリズムの一種である。シェルソートは、交換によるソート(バブルソート)あるいは挿入によるソート(挿入ソート)の一般化と見なすことができる[2]。ソートの方法は、まず、間隔の離れた要素の組に対してソートを行い、だんだんと比較する要素間の間隔を小さくしながらソートを繰り返す、というものである。離れた場所の要素からソートを始めることで、単純に近くの要素を比較する場合よりも速く、要素を所定の位置に移動させることができる。ただし、安定ソートではない。ドナルド・シェル(Donald L. Shell)が、1959年に、シェルソートの最初のバージョンを公開した[3][4] 。シェルソートの実行時間は、比較時に選ぶ間隔によって大きく異なる。多くの実用的な方法が提案されているが、正確な時間計算量を求める方法は、未解決問題である。

アルゴリズム[編集]

基本的な部分は、挿入ソートと同じである。挿入ソートは「ほとんど整列されたデータに対しては高速」という特長があるものの、「隣り合った要素同士しか交換しない」ため、あまり整列されていないデータに対しては低速であった。

そのため、適当な間隔をあけた飛び飛びのデータ列に対してあらかじめソートしておき、挿入ソートを適用すれば高速になると考えられる。この考え方を適用したのがシェルソートである。

  1. 適当な間隔 h を決める
  2. 間隔 h をあけて取り出したデータ列に挿入ソートを適用する
  3. 間隔 h を狭めて、2.を適用する操作を繰り返す
  4. h = 1 になったら、最後に挿入ソートを適用して終了

動作例[編集]

初期データ:

8 3 1 2 7 5 6 4

間隔4でみる。 色の同じところは、同じグループのデータ列である。

8 3 1 2 7 5 6 4

同じグループ内で挿入ソートし、間隔を2にする。

7 3 1 2 8 5 6 4

同じグループ内で挿入ソートし、間隔を1にする。

1 2 6 3 7 4 8 5

間隔1ということは、全体が同じ1つのグループということである。これを挿入ソートする。

1 2 3 4 5 6 7 8

計算時間[編集]

データの個数を  n とすると、計算時間は以下のようになる。

最悪計算時間 O(n \log^2 n)
最良計算時間 O(n)
平均計算時間 O(n^{1.25})
最悪空間計算量 O(n)

※ 間隔 h として、 1, 4, 13, 40, 121, \ldots, \frac{3^i - 1}{2}, \ldots < n という h_{i+1} = 3 h_{i} + 1 を満たす整数列を大きい方から採用すると、平均計算時間 O(n^{1.25}) になる。 [5]

脚注[編集]

  1. ^ Shellsort & Comparisons”. 2016年3月20日閲覧。
  2. ^ Knuth, Donald E. (1997). “Shell's method”. The Art of Computer Programming. Volume 3: Sorting and Searching (2nd ed.). Reading, Massachusetts: Addison-Wesley. pp. 83–95. ISBN 0-201-89685-0. 
  3. ^ Shell, D. L. (1959). “A High-Speed Sorting Procedure”. Communications of the ACM 2 (7): 30–32. doi:10.1145/368370.368387. http://penguin.ewu.edu/cscd300/Topic/AdvSorting/p30-shell.pdf. 
  4. ^ Some older textbooks and references call this the "Shell-Metzner" sort after Marlene Metzner Norton, but according to Metzner, "I had nothing to do with the sort, and my name should never have been attached to it." See Shell sort”. National Institute of Standards and Technology. 2007年7月17日閲覧。
  5. ^ Knuth, Donald E. (1997). “Shell's method”. The Art of Computer Programming. Volume 3: Sorting and Searching (2nd ed.). Reading, Massachusetts: Addison-Wesley. pp. 83–95. ISBN 0-201-89685-0.