シェルソート

ソートのアルゴリズムのひとつ

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

シェルソート
Step-by-step visualisation of Shellsort
間隔 23, 10, 4, 1 でのシェルソートの実行
クラス ソート
データ構造 配列
最悪計算時間 間隔に依存
最良計算時間 [1]
平均計算時間 間隔に依存
間隔については後述
最悪空間計算量 (in-place)
間隔5, 3, 1のシェルソートにおける要素の交換を示した図

アルゴリズム

編集

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

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

動作例

編集

初期データ:

8 3 1 2 7 5 6 4

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

8 3 1 2 7 5 6 4

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

7 3 1 2 8 5 6 4

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

1 2 6 3 7 4 8 5

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

1 2 3 4 5 6 7 8

間隔の決め方

編集

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

数列の一般項 (k ≥ 1) 実際の数列 最悪計算時間 備考
      ドナルド・シェルが最初に考案した数列。[2]

 が2の累乗の時、上記動作例と同一。

  ( 以下)     ドナルド・クヌース、 1973[3]

Pratt, 1971[6]に基づく。
平均計算時間は  [3][4]

      Sedgewick, 1982[7]
  ( )     Pratt, 1971[6]
既知の数列で最悪計算時間が最小となるもの。
間隔の狭め方が細かすぎるため、実用性は低い。[5]

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


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

脚注

編集
  1. ^ Shellsort & Comparisons”. 2016年3月20日閲覧。
  2. ^ a b c Shell, D. L. (1959). “A High-Speed Sorting Procedure”. Communications of the ACM 2 (7): 30–32. doi:10.1145/368370.368387. http://penguin.ewu.edu/cscd300/Topic/AdvSorting/p30-shell.pdf. 
  3. ^ a b c Knuth, Donald E. (1997). “Shell's method”. The Art of Computer Programming. Volume 3: Sorting and Searching (2nd ed.). Reading, Massachusetts: Addison-Wesley. pp. 83–95. ISBN 0-201-89685-0 
  4. ^ a b 渡部有隆、 秋葉拓哉 (2015). プログラミングコンテスト攻略のためのアルゴリズムとデータ構造. マイナビ. p. 77. ISBN 978-4-83995-295-2 
  5. ^ a b c Sedgewick, Robert (1996年). “Analysis of Shellsort and Related Algorithms”. 2021年8月5日閲覧。
  6. ^ a b Pratt, Vaughan Ronald (1979). Shellsort and Sorting Networks (Outstanding Dissertations in the Computer Sciences). Garland. ISBN 978-0-8240-4406-0. http://www.dtic.mil/get-tr-doc/pdf?AD=AD0740110 
  7. ^ Sedgewick, Robert (1998). Algorithms in C. 1 (3rd ed.). Addison-Wesley. pp. 273–281. ISBN 978-0-201-31452-6. https://archive.org/details/algorithmsinc00sedg/page/273