シェルソート

間隔5, 3, 1のシェルソートにおける要素の交換を示した図

シェルソート（改良挿入ソート、テンプレート:Lang-en）は、1959年にドナルド・シェルが開発したソートのアルゴリズム。挿入ソートの一般化であり、配列の中である程度間隔が離れた要素の組ごとに挿入ソートを行い、間隔を小さくしながら同様のソートを繰り返すことで高速化するアルゴリズムである。ただし、挿入ソートと異なり、安定ソートではなくなる。

アルゴリズム

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

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

動作例

初期データ:

8

3

1

2

7

5

6

4

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

8

テンプレート:Underline

テンプレート:Underline2

テンプレート:Underline2

7

テンプレート:Underline

テンプレート:Underline2

テンプレート:Underline2

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

テンプレート:Underline

3

テンプレート:Underline

2

テンプレート:Underline

5

テンプレート:Underline

4

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

1

2

6

3

7

4

8

5

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

1

2

3

4

5

6

7

8

間隔の決め方

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

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

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

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