シェルソート

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
シェルソート
クラス ソート
データ構造 配列
シェルソートアルゴリズムは、カラーバー

シェルソート改良挿入ソート)は、ドナルド・シェル(Donald L. Shell)が開発したソートアルゴリズム。高速だが、安定ソートではない。

アルゴリズム[編集]

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

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

  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}) になる。 [1]

脚注[編集]

  1. ^ 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.