シェルソート
間隔 23, 10, 4, 1 でのシェルソートの実行
クラスソート
データ構造配列
最悪計算時間
シェルソート(改良挿入ソート、英語: Shellsort, Shell sort, Shell's method)は、1959年にドナルド・シェルが開発した[2]ソートのアルゴリズム。挿入ソートの一般化[3]であり、配列の中である程度間隔が離れた要素の組ごとに挿入ソートを行い、間隔を小さくしながら同様のソートを繰り返すことで高速化するアルゴリズムである。ただし、挿入ソートと異なり、安定ソートではなくなる。目次 アルゴリズムの基本は挿入ソートと同じである。挿入ソートは「ほとんど整列されたデータに対しては高速」という長所を持つが、隣接した要素同士しか比較・交換を行わないため、あまり整列されていないデータに対しては低速であった。 初期データ: 83127564 この例では、間隔hを4→2→1(2の累乗)とする。 83127564 同じグループ内で挿入ソートし、h=2にする。 73128564 同じグループ内で挿入ソートし、h=1にする。 12637485 間隔が1ということは、全体が同じ1つのグループということである。これを挿入ソートする。 12345678 シェルソートの実行時間(時間計算量)は、比較時に選ぶ間隔hによって大きく異なる。 数列の一般項 (k ? 1)実際の数列最悪計算時間備考 n {\displaystyle n} が2の累乗の時、上記動作例と同一。 Pratt, 1971[6]に基づく。 これらの数列をソートの間隔として利用する際は、(要素数以内で)大きな数字から狭めていく。 3 k − 1 2 {\displaystyle {\frac {3^{k}-1}{2}}} を使う場合、間隔hを121→40→13→4→1とする(hを3で整数除算していけばよい)。
1 アルゴリズム
2 動作例
3 間隔の決め方
4 C++による実装例
5 脚注
アルゴリズム
シェルソートは、「飛び飛びの列を繰り返しソートして、配列を大まかに整列された状態に近づけていく」ことにより、挿入ソートの長所を活かしたものである。
アルゴリズムの概略は次のとおりである。
適当な間隔 h {\displaystyle h} を決める(hの決め方については後述)
間隔 h {\displaystyle h} をあけて取り出したデータ列に挿入ソートを適用する
間隔 h {\displaystyle h} を狭めて、2.を適用する操作を繰り返す
h = 1 {\displaystyle h=1} になったら、最後に挿入ソートを適用して終了
動作例
まず、h=4とする。色の同じ部分は、同じグループのデータ列である。
間隔の決め方
前節の例ではhを2の累乗としたが、この場合、最悪計算量が O ( n 2 ) {\displaystyle \mathrm {O} (n^{2})} となってしまう。[2]各周回で同じ位置の要素ばかりが比較交換されるため、h=1となった段階で「全体が大まかに整列されている」という仮定が成り立たなくなるためである。[4]
より効率の良い(計算量の少ない)ソートを行うために、様々な間隔が提案されてきた。[5]以下の表は、間隔を決定するための数列の例である。( n {\displaystyle n} は要素数)
⌊ n 2 k ⌋ {\displaystyle \left\lfloor {\frac {n}{2^{k}}}\right\rfloor } ⌊ n 2 ⌋ , ⌊ n 4 ⌋ , … , 1 {\displaystyle \left\lfloor {\frac {n}{2}}\right\rfloor ,\left\lfloor {\frac {n}{4}}\right\rfloor ,\ldots ,1} O ( n 2 ) {\displaystyle \mathrm {O} (n^{2})} ドナルド・シェルが最初に考案した数列。[2]
3 k − 1 2 {\displaystyle {\frac {3^{k}-1}{2}}} ( ⌈ n 3 ⌉ {\displaystyle \left\lceil {\frac {n}{3}}\right\rceil } 以下) 1 , 4 , 13 , 40 , 121 , … {\displaystyle 1,4,13,40,121,\ldots } O ( n 3 2 ) = O ( n 1.5 ) {\displaystyle \mathrm {O} \left(n^{\frac {3}{2}}\right){=}\mathrm {O} (n^{1.5})} ドナルド・クヌース、 1973[3]
平均計算時間は O ( n 1.25 ) {\displaystyle \mathrm {O} (n^{1.25})} 。[3][4]
A 0 = 1 , A k = 4 k + 3 ⋅ 2 k − 1 + 1 {\displaystyle A_{0}{=}1,A_{k}{=}4^{k}+3\cdot 2^{k-1}+1} 1 , 8 , 23 , 77 , 281 , … {\displaystyle 1,8,23,77,281,\ldots } O ( n 4 3 ) = O ( n 1.33 … ) {\displaystyle \mathrm {O} \left(n^{\frac {4}{3}}\right){=}\mathrm {O} (n^{1.33\ldots })} Sedgewick, 1982[7]
2 p 3 q {\displaystyle 2^{p}3^{q}} ( p ≥ 0 , q ≥ 0 {\displaystyle p\geq 0,q\geq 0} ) 1 , 2 , 3 , 4 , 6 , 8 , 9 , 12 , … {\displaystyle 1,2,3,4,6,8,9,12,\ldots } O ( n log 2 n ) {\displaystyle \mathrm {O} \left(n\log ^{2}n\right)} Pratt, 1971[6]
既知の数列で最悪計算時間が最小となるもの。
間隔の狭め方が細かすぎるため、実用性は低い。[5]
様々な間隔の計算量について理論的に考察されているが、現状、どのような間隔が最適か(例えば、平均 O ( n log n ) {\displaystyle \mathrm {O} (n\log n)} 時間となる数列があるか)は未解決問題である[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日閲覧。
Size:23 KB
出典: フリー百科事典『ウィキペディア(Wikipedia)』
担当:undef