シェルソート【Shell sort】

概要

シェルソート（Shell sort）とは、与えられたデータ列を大小などの順序通りになるよう並べ替えるソート(整列)アルゴリズムの最も基本的な手法の一つで、挿入ソートを改良したもの。1959年にアメリカのコンピュータ科学者ドナルド・シェル(Donald Shell)が考案した。

挿入ソートは未整列の要素を一つずつ、整列済みの列の適切な位置を探して挿入していく手法である。与えられた列が整列済みに近ければ高速に整列できる一方、逆順に近い場合には極端に遅くなる弱点があった。

シェルソートでは等間隔で離れている飛び飛びの要素同士を一つのグループとし、グループ内で挿入ソートを行う。例えば、間隔が3なら3n番目のグループ、3n+1番目のグループ、3n+2番目のグループの3つに分け、それぞれの中で整列する。

このグループごとの整列を、次第に間隔を狭めながら何度も繰り返す。最後に間隔1ですべての要素を対象に挿入ソートを実行すれば、全体の整列が完了する。飛び飛びの整列を行うことで全体が大まかに整列され、挿入ソートの弱点である「逆順に近い状態」を緩和することができる。

間隔の選択の仕方、繰り返しごとの狭め方により計算時間が異なる。当初シェルが考案した手法では、要素数nに対して「n/2,n/4,…,1」のように繰り返しごとに半分になっていく方式だが、これだと最悪計算時間が O（n²）となってしまうことが知られている。様々な手法が提唱されており、実用上は（…,121,40,13,4,1）となる（3^k-1）/2 などが用いられる。

挿入ソートでは完全な逆順の場合に O（n²）かかってしまうが、現在知られている最良の間隔決定法では最悪計算時間が O（nlog²n）となることが分かっている。最良計算時間はすでにソート済みの要素列を扱う場合で、挿入ソートと同じ O（n）である。

挿入ソートは同じ大きさの要素の順序が保存される安定ソートだが、シェルソートは順序の維持が保証されない不安定ソートである。整列したいデータ列以外の記憶領域を用意しなくてよいインプレースソート（内部ソート）である点は挿入ソートと変わらない。

(2024.3.7更新)