シェルソート

シェルソート

間隔 23, 10, 4, 1 でのシェルソートの実行
クラス	ソート
データ構造	配列
最悪計算時間	間隔に依存
最良計算時間	${\displaystyle \mathrm {O} (n\log n)}$[1]
平均計算時間	間隔に依存 間隔については後述
最悪空間計算量	${\displaystyle \mathrm {O} (1)}$(in-place)

シェルソート（改良挿入ソート、英語: Shellsort, Shell sort, Shell's method）は、1959年にドナルド・シェルが開発した^[2]ソートのアルゴリズム。挿入ソートの一般化^[3]であり、配列の中である程度間隔が離れた要素の組ごとに挿入ソートを行い、間隔を小さくしながら同様のソートを繰り返すことで高速化するアルゴリズムである。ただし、挿入ソートと異なり、安定ソートではなくなる。

アルゴリズムの基本は挿入ソートと同じである。挿入ソートは「ほとんど整列されたデータに対しては高速」という長所を持つが、隣接した要素同士しか比較・交換を行わないため、あまり整列されていないデータに対しては低速であった。
シェルソートは、「飛び飛びの列を繰り返しソートして、配列を大まかに整列された状態に近づけていく」ことにより、挿入ソートの長所を活かしたものである。
アルゴリズムの概略は次のとおりである。

1. 適当な間隔 ${\displaystyle h}$ を決める（hの決め方については後述）
2. 間隔 ${\displaystyle h}$ をあけて取り出したデータ列に挿入ソートを適用する
3. 間隔 ${\displaystyle h}$ を狭めて、2.を適用する操作を繰り返す
4. ${\displaystyle h=1}$ になったら、最後に挿入ソートを適用して終了

初期データ:

この例では、間隔hを4→2→1（2の累乗）とする。
まず、h=4とする。色の同じ部分は、同じグループのデータ列である。

同じグループ内で挿入ソートし、h=2にする。

同じグループ内で挿入ソートし、h=1にする。

間隔が1ということは、全体が同じ1つのグループということである。これを挿入ソートする。

シェルソートの実行時間（時間計算量）は、比較時に選ぶ間隔hによって大きく異なる。
前節の例ではhを2の累乗としたが、この場合、最悪計算量が${\displaystyle \mathrm {O} (n^{2})}$となってしまう。^[2]各周回で同じ位置の要素ばかりが比較交換されるため、h=1となった段階で「全体が大まかに整列されている」という仮定が成り立たなくなるためである。^[4]
より効率の良い（計算量の少ない）ソートを行うために、様々な間隔が提案されてきた。^[5]以下の表は、間隔を決定するための数列の例である。（${\displaystyle n}$は要素数）

数列の一般項 (k ≥ 1)	実際の数列	最悪計算時間	備考
${\displaystyle \left\lfloor {\frac {n}{2^{k}}}\right\rfloor }$	${\displaystyle \left\lfloor {\frac {n}{2}}\right\rfloor ,\left\lfloor {\frac {n}{4}}\right\rfloor ,\ldots ,1}$	${\displaystyle \mathrm {O} (n^{2})}$	ドナルド・シェルが最初に考案した数列。[2] ${\displaystyle n}$が2の累乗の時、上記動作例と同一。
${\displaystyle {\frac {3^{k}-1}{2}}}$　（${\displaystyle \left\lceil {\frac {n}{3}}\right\rceil }$以下）	${\displaystyle 1,4,13,40,121,\ldots }$	${\displaystyle \mathrm {O} \left(n^{\frac {3}{2}}\right){=}\mathrm {O} (n^{1.5})}$	ドナルド・クヌース、 1973[3] Pratt, 1971[6]に基づく。 平均計算時間は ${\displaystyle \mathrm {O} (n^{1.25})}$。[3][4]
${\displaystyle A_{0}{=}1,A_{k}{=}4^{k}+3\cdot 2^{k-1}+1}$	${\displaystyle 1,8,23,77,281,\ldots }$	${\displaystyle \mathrm {O} \left(n^{\frac {4}{3}}\right){=}\mathrm {O} (n^{1.33\ldots })}$	Sedgewick, 1982[7]
${\displaystyle 2^{p}3^{q}}$ (${\displaystyle p\geq 0,q\geq 0}$)	${\displaystyle 1,2,3,4,6,8,9,12,\ldots }$	${\displaystyle \mathrm {O} \left(n\log ^{2}n\right)}$	Pratt, 1971[6] 既知の数列で最悪計算時間が最小となるもの。 間隔の狭め方が細かすぎるため、実用性は低い。[5]

これらの数列をソートの間隔として利用する際は、（要素数以内で）大きな数字から狭めていく。${\displaystyle {\frac {3^{k}-1}{2}}}$を使う場合、間隔hを121→40→13→4→1とする（hを3で整数除算していけばよい）。
様々な間隔の計算量について理論的に考察されているが、現状、どのような間隔が最適か（例えば、平均${\displaystyle \mathrm {O} (n\log n)}$時間となる数列があるか）は未解決問題である^[5]。

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);
}

表 話 編 歴 ソート
理論	計算複雑性理論 ランダウの記号 全順序 リスト 安定性 ソーティングネットワーク 比較ソート（英語版） 整数ソート（英語版）
交換ソート	バブルソート シェーカーソート 奇偶転置ソート コムソート ノームソート 比例拡張ソート（英語版） クイックソート
選択ソート	選択ソート ヒープソート スムースソート（英語版） デカルト木ソート（英語版） トーナメントソート（英語版） サイクルソート（英語版）
挿入ソート	挿入ソート シェルソート ツリーソート（英語版） 図書館ソート ペイシェンスソート（英語版）
マージソート	マージソート 多層マージソート（英語版） ストランドソート（英語版）
非比較ソート	基数ソート バケットソート 計数ソート プロキシマップソート（英語版） 鳩の巣ソート バーストソート（英語版） ビーズソート
並行ソート	バイトニックソート バッチャー奇偶マージソート シェアソート サンプルソート（英語版）
混成ソート	ティムソート（英語版） イントロソート アンシャッフルソート（英語版）
その他	トポロジカルソート パンケーキソート（英語版） スパゲティソート
非効率的/ ユーモラスソート	ボゴソート ストゥージソート スリープソート スローソート（英語版） エラーソート
カテゴリ