シェルソート（改良挿入ソート、）は、1959年にドナルド・シェルが開発したソートのアルゴリズム。挿入ソートの一般化であり、配列の中である程度間隔が離れた要素の組ごとに挿入ソートを行い、間隔を小さくしながら同様のソートを繰り返すことで高速化するアルゴリズムである。ただし、挿入ソートと異なり、安定ソートではなくなる。
アルゴリズム アルゴリズムの基本は挿入ソートと同じである。挿入ソートは「ほとんど整列されたデータに対しては高速」という長所を持つが、隣接した要素同士しか比較・交換を行わないため、あまり整列されていないデータに対しては低速であった。 シェルソートは、「飛び飛びの列を繰り返しソートして、配列を大まかに整列された状態に近づけていく」ことにより、挿入ソートの長所を活かしたものである。 アルゴリズムの概略は次のとおりである。
適当な間隔 を決める（hの決め方については後述） 間隔 をあけて取り出したデータ列に挿入ソートを適用する 間隔 を狭めて、2.を適用する操作を繰り返す になったら、最後に挿入ソートを適用して終了
動作例 初期データ: 8 3 1 2 7 5 6 4
この例では、間隔hを4→2→1（2の累乗）とする。 まず、h=4とする。色の同じ部分は、同じグループのデータ列である。 8 7
同じグループ内で挿入ソートし、h=2にする。 3 2 5 4
同じグループ内で挿入ソートし、h=1にする。 1 2 6 3 7 4 8 5
間隔が1ということは、全体が同じ1つのグループということである。これを挿入ソートする。 1 2 3 4 5 6 7 8
間隔の決め方 シェルソートの実行時間（時間計算量）は、比較時に選ぶ間隔hによって大きく異なる。 前節の例ではhを2の累乗としたが、この場合、最悪計算量がとなってしまう。各周回で同じ位置の要素ばかりが比較交換されるため、h=1となった段階で「全体が大まかに整列されている」という仮定が成り立たなくなるためである。 より効率の良い（計算量の少ない）ソートを行うために、様々な間隔が提案されてきた。以下の表は、間隔を決定するための数列の例である。（は要素数）
{| class="wikitable" |- style="background-color: #efefef;" ! 数列の一般項 (k ≥ 1) ! 実際の数列 ! 最悪計算時間 ! 備考
| ドナルド・シェルが最初に考案した数列。 が2の累乗の時、上記動作例と同一。
| （以下）
| ドナルド・クヌース、 1973 Pratt, 1971に基づく。 平均計算時間は 。
| , 1982
| ()
| Pratt, 1971既知の数列で最悪計算時間が最小となるもの。間隔の狭め方が細かすぎるため、実用性は低い。
これらの数列をソートの間隔として利用する際は、（要素数以内で）大きな数字から狭めていく。を使う場合、間隔hを121→40→13→4→1とする（hを3で整数除算していけばよい）。 様々な間隔の計算量について理論的に考察されているが、現状、どのような間隔が最適か（例えば、平均時間となる数列があるか）は未解決問題である。
C++による実装例 template <typename RandomAccessIterator, typename Compare> void shellsort(RandomAccessIterator first, RandomAccessIterator last, Compare comp, const double sk = 3.14159265358979323846264338327950, const short m = 5) { if(first == last) return; double gap = distance(first, last); std::ptrdiff_t h;
do
gap /= sk; h = (std::ptrdiff_t)(gap + 0.5); if(h < m) h = 1; RandomAccessIterator H = first + h; for(RandomAccessIterator i = H; i < last; ++i)
if(comp(*i, *(i - h)))
auto t = std::move(*i); RandomAccessIterator j = i; do
*j = std::move(*(j - h)); j -= h; }while(H <= j && comp(t, *(j - h))); *j = std::move(t);
}while(1 < h); }
脚注