シェルソート
出典: フリー百科事典『ウィキペディア（Wikipedia）』
シェルソート（改良挿入ソート）は、Donald L. Shellが開発したソートのアルゴリズム。高速だが、安定ソートではない。
[編集] アルゴリズム
基本的な部分は、挿入ソートと同じである。挿入ソートは「ほとんど整列されたデータに対しては高速」という特長があるものの、「隣り合った要素同士しか交換しない」ため、あまり整列されていないデータに対しては低速であった。
そのため、適当な間隔をあけた飛び飛びのデータ列に対してあらかじめソートしておき、挿入ソートを適用すれば高速になると考えられる。この考え方を適用したのがシェルソートである。
- 適当な間隔hを決める
- 間隔hをあけて取り出したデータ列に挿入ソートを適用する
- 間隔hを狭めて、2.を適用する操作を繰り返す
- 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 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
[編集] 実行時間
間隔hとして、h=1, 4, 13, 40, 121,...という、hn+1=3hn+1を満たす整数列を用いて、hを大きい方から適用すると、計算時間O(n1.25)程度になる。
