シェルソート

テンプレート:Infobox algorithm シェルソート（改良挿入ソート）は、ドナルド・シェル（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

実行時間

間隔hとして、h=1, 4, 13, 40, 121,...という、h_n+1=3h_n+1を満たす整数列を用いて、hを大きい方から適用すると、計算時間O(n^1.25)程度になる。