シェルソート

シェルソート

間隔 23, 10, 4, 1 でのシェルソートの実行
クラス	ソート
データ構造	配列
最悪計算時間	O(n2)
最良計算時間	O(n log n)
平均計算時間	使用する間隔列に依存
最悪空間計算量	О(n) total, O(1) auxiliary

シェルソートアルゴリズムは、カラーバー

シェルソート（改良挿入ソート、英語: Shellsort, Shell sort, Shell's method）は、in-placeな比較ソートのアルゴリズムの一種である。シェルソートは、交換によるソート（バブルソート）あるいは挿入によるソート（挿入ソート）の一般化と見なすことができる。ソートの方法は、まず、間隔の離れた要素の組に対してソートを行い、だんだんと比較する要素間の間隔を小さくしながらソートを繰り返す、というものである。離れた場所の要素からソートを始めることで、単純に近くの要素を比較する場合よりも速く、要素を所定の位置に移動させることができる。ただし、安定ソートではない。ドナルド・シェル（Donald L. Shell）が、1959年に、シェルソートの最初のバージョンを公開した 。シェルソートの実行時間は、比較時に選ぶ間隔によって大きく異なる。多くの実用的な方法が提案されているが、正確な時間計算量を求める方法は、未解決問題である。

アルゴリズム

基本的な部分は、挿入ソートと同じである。挿入ソートは「ほとんど整列されたデータに対しては高速」という特長があるものの、「隣り合った要素同士しか交換しない」ため、あまり整列されていないデータに対しては低速であった。

そのため、適当な間隔をあけた飛び飛びのデータ列に対してあらかじめソートしておき、挿入ソートを適用すれば高速になると考えられる。この考え方を適用したのがシェルソートである。

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

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

動作例

初期データ:

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

計算時間

データの個数を $n$ とすると、計算時間は以下のようになる。

最良計算時間	$O(n\log n)$
最悪計算時間	$O(n^{2})$
平均計算時間	$O(n^{1.25})$
空間計算量	$O(n)$

※ 間隔 $h$ として、 $1,4,13,40,121,\ldots ,{\frac {3^{i}-1}{2}},\ldots <n$ という $h_{i+1}=3h_{i}+1$ を満たす整数列を大きい方から採用すると、平均計算時間 $O(n^{1.25})$ になる。