シェルソート
![]() 間隔 23, 10, 4, 1 でのシェルソートの実行 | |
クラス | ソート |
---|---|
データ構造 | 配列 |
最悪計算時間 | 間隔に依存 |
最良計算時間 | [1] |
平均計算時間 | 間隔に依存 間隔については後述 |
最悪空間計算量 | (in-place) |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/4c/Shell_sorting_algorithm_color_bars.svg/220px-Shell_sorting_algorithm_color_bars.svg.png)
シェルソート(改良挿入ソート、英語: Shellsort, Shell sort, Shell's method)は、1959年にドナルド・シェルが開発した[2]ソートのアルゴリズム。挿入ソートの一般化[3]であり、配列の中である程度間隔が離れた要素の組ごとに挿入ソートを行い、間隔を小さくしながら同様のソートを繰り返すことで高速化するアルゴリズムである。ただし、挿入ソートと異なり、安定ソートではなくなる。
アルゴリズム
アルゴリズムの基本は挿入ソートと同じである。挿入ソートは「ほとんど整列されたデータに対しては高速」という長所を持つが、隣接した要素同士しか比較・交換を行わないため、あまり整列されていないデータに対しては低速であった。
シェルソートは、「飛び飛びの列を繰り返しソートして、配列を大まかに整列された状態に近づけていく」ことにより、挿入ソートの長所を活かしたものである。
アルゴリズムの概略は次のとおりである。
- 適当な間隔 を決める(hの決め方については後述)
- 間隔 をあけて取り出したデータ列に挿入ソートを適用する
- 間隔 を狭めて、2.を適用する操作を繰り返す
- になったら、最後に挿入ソートを適用して終了
動作例
初期データ:
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); }
脚注
- ^ “Shellsort & Comparisons”. 2016年3月20日閲覧。
- ^ 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.
- ^ 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
- ^ a b 渡部有隆、 秋葉拓哉 (2015). プログラミングコンテスト攻略のためのアルゴリズムとデータ構造. マイナビ. p. 77. ISBN 978-4-83995-295-2
- ^ a b c Sedgewick, Robert (1996年). “Analysis of Shellsort and Related Algorithms”. 2021年8月5日閲覧。
- ^ 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
- ^ 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