シェルソート

出典: フリー百科事典『ウィキペディア(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

実行時間[編集]

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