シェルソート

シェルソート

シェルソートのギャップ23、10、4、1のアクション
クラス	ソートアルゴリズム
データ構造	配列
最悪の場合の パフォーマンス	O( n 2 ) (最悪の既知のギャップシーケンス) O( n log 2 n ) (最良の既知の最悪のギャップシーケンス) [1]
最高の パフォーマンス	O( n log n ) (最も多いギャップシーケンス) O( n log 2 n ) (最もよく知られている最悪のギャップシーケンス) [2]
平均的 なパフォーマンス	ギャップシーケンスに依存する
最悪の場合の 空間複雑度	О( n ) 合計、O(1) 補助
最適	いいえ

シェルソートは、シェルソートまたはシェル法とも呼ばれ、インプレース 比較ソートです。これは、交換によるソート（バブルソート）または挿入によるソート（挿入ソート）の一般化として考えることができます。^[3]この方法では、まず互いに離れた要素のペアをソートし、次に比較する要素間のギャップを徐々に減らしていきます。離れた要素から始めることで、単純な最近傍交換よりも速く、一部の位置外れの要素を所定の位置に移動することができます。ドナルド・シェルは、 1959年にこのソートの最初のバージョンを発表しました。^{[4] [5]シェルソートの実行時間は、使用するギャップシーケンスに大きく依存します。多くの実用的な変種では、その}時間計算量を決定することが未解決の問題となっています。

シェルソートは挿入ソートの最適化で、離れた項目の交換を可能にします。アイデアは、どこから始めてもh番目の要素ごとにソートされたリストが生成されるように要素のリストを整理することです。このようなリストはhソートされていると言われます。また、それぞれが個別にソートされたh個のインターリーブ リストと考えることもできます。^[6] hの値を大きくして開始すると、元のリスト内で要素が長距離を移動できるため、大量の無秩序がすぐに軽減され、より小さなhソート ステップで行う作業が少なくなります。^[7]次に、リストを小さな整数kでk ソートすると、リストはhソートされたままになります。 h = 1での最終ソートにより、 最後にリストが完全にソートされることが保証されますが、^[6] h値の減少シーケンスを慎重に選択すると、この最終パスで行う作業がほとんど残りません。

簡単に言えば、1024 個の数字の配列がある場合、最初のギャップ ( h ) は 512 になる可能性があるということです。次に、リスト全体にわたって、前半の各要素を後半の要素と比較します。2 番目のギャップ ( k ) は 256 で、配列は 4 つのセクション (0、256、512、768 から始まる) に分割され、各セクションの最初の項目が互いに相対的に並べ替えられていることを確認し、次に各セクションの 2 番目の項目を並べ替える、というように続きます。実際には、ギャップのシーケンスは任意にすることができますが、最後のギャップは常に 1 で並べ替えが完了します (実質的に通常の挿入並べ替えで終了します)。

ギャップ 5、3、1 での Shellsort の実行例を以下に示します。

最初のパスである 5 ソートでは、5 つの個別のサブ配列 ( a ₁、a ₆、a ₁₁ )、 ( a ₂、a ₇、a ₁₂ )、 ( a ₃、a ₈ )、 ( a ₄、a ₉ )、 ( a ₅、a ₁₀ ) に対して挿入ソートを実行します。たとえば、サブ配列 ( a ₁、a ₆、a ₁₁ ) は (62、 17、 25) から (17、 25、 62) に変更されます。次のパスである 3 ソートでは、3 つのサブ配列 ( a ₁、a ₄、a ₇、a ₁₀ )、 ( a ₂、a ₅、a ₈、a ₁₁ )、 ( a ₃、a ₆、a ₉、a ₁₂ ) に対して挿入ソートを実行します。最後のパスである 1 ソートは、配列全体 ( a ₁、...、a ₁₂ ) の通常の挿入ソートです。

例が示すように、Shellsort が操作するサブ配列は最初は短く、後で長くなりますが、ほぼ順序付けられます。どちらの場合も、挿入ソートは効率的に機能します。

挿入ソートとは異なり、シェルソートは安定したソートではありません。ギャップのある挿入によって等しい要素が互いに通過し、元の順序が失われるためです。これは、入力が部分的にソートされている場合に実行速度が速くなるという点で、 適応ソート アルゴリズムです。

内部挿入ソートを使用した Marcin Ciura のギャップシーケンスを使用します。

# 配列 a[0...n-1] をソートします。
gaps = [ 701 , 301 , 132 , 57 , 23 , 10 , 4 , 1 ] # Ciuraギャップシーケンス              

# 最大のギャップから始めて、ギャップ 1 まで処理します
# 挿入ソートに似ていますが、各ステップで 1 ではなくギャップが使用されます
foreach ( gap in gaps ) { # gaps 内のすべての要素に対してギャップ付き挿入ソートを実行します# 各ループでは a[0..gap-1] がギャップ順になりますfor ( i = gap ; i < n ; i += 1 ) { # a[i] を temp に保存し、位置 i に穴を開けますtemp = a [ i ] # a[i] の正しい位置が見つかるまで、以前にギャップソートされた要素を上にシフトしますfor ( j = i ; ( j >= gap ) && ( a [ j - gap ] > temp ); j -= gap ) { a [ j ] = a [ j - gap ] } # temp (元の a[i]) を正しい位置に配置しますa [ j ] = temp } }   

    
    
             
    
        
          
        
                       
        
                
        
        
          
    

どのギャップ シーケンスを使用するかを決定するのは困難です。1 を含むすべてのギャップ シーケンスは正しいソートを生成します (これにより、最終パスが通常の挿入ソートになります)。ただし、このようにして得られた Shellsort のバージョンの特性は大きく異なる場合があります。ギャップが少なすぎるとパスが遅くなり、ギャップが多すぎるとオーバーヘッドが発生します。

以下の表は、これまでに公開されたほとんどの提案されたギャップシーケンスを比較したものです。これらの中には、ソートされた配列のサイズ ( N ) に応じて減少する要素を持つものがあります。その他は増加する無限シーケンスで、 N未満の要素は逆の順序で使用する必要があります。

Nのバイナリ表現に連続するゼロが多数含まれる場合、Shell のオリジナルのギャップ シーケンスを使用する Shellsort では、最悪の場合、Θ( N ² ) 回の比較が行われます。たとえば、Nが 2 の累乗に等しい場合、中央値より大きい要素と小さい要素がそれぞれ奇数位置と偶数位置を占めるときに、最後のパスでのみ比較されるため、このケースが発生します。

比較ソートに最適なO ( N  log  N )よりも複雑度は高くなりますが、 Pratt のバージョンはソート ネットワークに適しており、 Batcher のビトニック ソーターと同じ漸近ゲート複雑度を持ちます。

Gonnet と Baeza-Yates は、連続するギャップの比率がおよそ 2.2 に等しいときに、Shellsort が平均して比較回数が最も少なくなることを観察しました。^[13]これが、比率 2.2 のシーケンスと比率 2.25 の Tokuda のシーケンスが効率的である理由です。ただし、なぜそうなるのかはわかっていません。Sedgewick は、最大公約数が低いギャップ、または互いに素なギャップを使用することを推奨しています。^{[18] [検証失敗]}奇数のギャップは実際にはうまく機能しているようです。偶数のギャップを避けることで 25% の削減が観測されています。3 と 5 の倍数のギャップを避けると、10% 未満の小さな利点が得られるようです。^{[独自の研究? ]}

平均比較回数に関しては、Ciuraのシーケンス^[15]が最も優れた性能を持っていることが知られています。701を超えるギャップは決定されませんでしたが、シーケンスは再帰式に従ってさらに拡張できます。 ${\displaystyle h_{k}=\lfloor 2.25h_{k-1}\rfloor }$

単純な式 （ここで、 ）で定義される徳田数列は、実際の用途に推奨できます。 ${\displaystyle h_{k}=\lceil h'_{k}\rceil }$${\displaystyle h'_{k}=2.25h'_{k-1}+1}$${\displaystyle h'_{1}=1}$

最大入力サイズが小さい場合（シェルソートをクイックソートやマージソートなどの他の再帰ソートアルゴリズムによって小さなサブ配列に使用する場合に発生する可能性がある）、各入力サイズに対して最適なシーケンスを作成することができます。^{[19] [20]}

次の特性が成り立ちます。任意のh _{1ソート済み配列を}h ₂ソートした後、配列はh ₁ソートされたままです。^[21]すべてのh ₁ソート済みおよびh ₂ソート済み配列は、任意の非負整数a ₁およびa _{2に対して、(} a ₁ h ₁ + a ₂ h ₂ ) ソート済みでもあります。したがって、シェルソートの最悪ケースの複雑性はフロベニウス問題に関連しています。gcd = 1の整数h ₁、...、h _nが与えられた場合、フロベニウス数g ( h ₁、...、h _n ) は、非負整数a ₁、...、a _nでa ₁ h ₁ + ... + a _{n h n}として表すことができない最大の整数です。フロベニウス数の既知の公式を使用して、いくつかのクラスのギャップシーケンスについてシェルソートの最悪ケースの複雑性を決定できます。^{[22]証明さ}れた結果は上記の表に示されています。

マーク・アレン・ワイスは、入力配列が逆順の場合、シェルソートはO(NlogN )時間で実行されることを証明した。 ^[23]

平均演算回数に関しては、実証された結果のいずれも実際のギャップシーケンスには関係ありません。2の累乗であるギャップについては、Espelidはこの平均を と計算しました。^[24] Knuthは、 2つのギャップ( h、1)を持つN要素配列のソートの平均複雑度を と決定しました。^[3]したがって、h = Θ( N ^1/3 )の2パスシェルソートは、平均してO ( N ^5/3 )の比較/反転/実行時間になります。Yaoは、3パスシェルソートの平均複雑度を見つけました。^{[25]彼の結果は}JansonとKnuthによって改良されました: ^[26] 3つのギャップ( ch、cg、1)を持つシェルソート中の平均比較/反転/実行時間( hとgは互いに素)は、最後の式のψ ( h , g )は、漸近的に等しい複雑な関数です。特に、h = Θ( N7 ^/15 )かつg = Θ( N1 ^/5 )のとき、ソートの平均時間はO ( N23 ^/15 )です。 ${\displaystyle 0.5349N{\sqrt {N}}-0.4387N-0.097{\sqrt {N}}+O(1)}$ ${\displaystyle {\frac {2N^{2}}{h}}+{\sqrt {\pi N^{3}h}}}$${\displaystyle {\frac {N^{2}}{4ch}}+O(N)}$${\displaystyle {\frac {1}{8g}}{\sqrt {\frac {\pi }{ch}}}(h-1)N^{3/2}+O(hN)}$${\displaystyle \psi (h,g)N+{\frac {1}{8}}{\sqrt {\frac {\pi }{c}}}(c-1)N^{3/2}+O\left((c-1)gh^{1/2}N\right)+O\left(c^{2}g^{3}h^{2}\right)}$${\displaystyle {\sqrt {\frac {\pi h}{128}}}g+O\left(g^{-1/2}h^{1/2}\right)+O\left(gh^{-1/2}\right)}$

実験に基づいて、ヒバードのギャップシーケンスを使用したシェルソートは平均O ( N ^5/4 ) 時間で実行され、^[3]ゴネットとバエザ・イェーツのシーケンスでは平均 0.41 N  ln  N  (ln ln  N  + 1/6) の要素移動が必要であると推測されています。^[13]ソートされた配列に数百万の要素が含まれている場合、以前に他のシーケンスに対して提案された平均操作数の近似値は失敗します。

下のグラフは、さまざまなギャップシーケンスで使用される要素比較の平均数を理論上の下限値、つまり log ₂ Nで割った値を示しています。Ciuria のシーケンス 1、4、10、23、57、132、301、701 (Ci01 と表示) は、式 に従って拡張されています。 ${\displaystyle h_{k}=\lfloor 2.25h_{k-1}\rfloor }$

コルモゴロフ複雑度の理論を適用して、Jiang、Li、およびVitányi ^{[27] は、}pパス Shellsortでの平均操作数/実行時間の順序の下限を次のように証明しました。 p  ≤ log ₂ Nの場合、Ω( pN ^{1+1/ p} ) 、 p  > log ₂ Nの場合、Ω( pN )です。したがって、Shellsort は、ギャップ数が配列サイズの対数に比例して増加するギャップシーケンスを使用する場合にのみ、N log Nのように漸近的に増加する平均時間で実行できる見込みがあります。ただし、 Shellsort が、比較ソートに最適な平均ケース複雑度のこの漸近順序に到達できるかどうかは不明です。下限 は、まで のパス数ごとにVitányi ^[28]によって改善されました。実際、平均ケースで現在知られているすべての境界（下限と上限）は、この下限と正確に一致しています。たとえば、Janson-Knuth の上限は、使用された増分シーケンスの結果の下限と一致するという新しい結果が得られ、この増分シーケンスの 3 パス シェルソートでは比較/反転/実行時間が使用されていることがわかります。この式を使用すると、下限が不明な増分シーケンスを検索できます。たとえば、4 パスの増分シーケンスでは、 増分シーケンスの 下限が より大きい場合です。下限は次のようになります。 ${\displaystyle p}$${\displaystyle \Omega (N\sum _{k=1}^{p}h_{k-1}/h_{k})}$${\displaystyle h_{0}=N}$${\displaystyle p}$${\displaystyle \Theta (N^{23/15})}$${\displaystyle \Omega (pn^{1+1/p})=\Omega (n^{5/4})}$${\displaystyle h_{1}=n^{11/16},}$ ${\displaystyle h_{2}=n^{7/16},}$ ${\displaystyle h_{3}=n^{3/16},}$ ${\displaystyle h_{4}=1}$${\displaystyle T=\Omega (n\cdot (n^{1-11/16}+n^{11/16-7/16}+n^{7/16-3/16}+n^{3/16})=\Omega (n^{1+5/16})=\Omega (n^{21/16}).}$

シェルソートのどのバージョンでも、最悪の場合の複雑度はより高次のものである。プラクストン、プーネン、スールは、それが少なくとも と同じ速さで増加することを示した。^{[29] [30]}ロバート・サイファーは、すべての に対してとなる より強い下限を証明した。^[31]${\displaystyle \Omega \left(N\left({\log N \over \log \log N}\right)^{2}\right)}$${\displaystyle \Omega \left(N{{(\log N)^{2}} \over {\log \log N}}\right)}$${\displaystyle h_{s+1}>h_{s}}$${\displaystyle s}$

Shellsortはクイックソートよりも多くの操作を実行し、キャッシュミス率も高い。しかし、少ないコードで実装でき、コールスタックも使用しないため、組み込みシステム向けのC標準ライブラリのqsort関数の実装では、クイックソートの代わりにShellsortを使用している。たとえば、uClibcライブラリではShellsortが使用されている。^[32]同様の理由で、過去にはLinuxカーネルでもShellsortが使用されていた。^[33]

Shellsortは、短いサブ配列をソートしたり、再帰の深さが指定された制限を超えたときに速度低下を防ぐための、イントロスペクティブソートのサブアルゴリズムとしても機能します。この原理は、たとえばbzip2コンプレッサで採用されています。^[34]

• コームソート

• Knuth, Donald E. (1997)。「シェル法」。コンピュータプログラミングの技法。第 3 巻: ソートと検索(第 2 版)。マサチューセッツ州レディング: Addison-Wesley。pp. 83–95。ISBN 978-0-201-89685-5。
• Shellsort および関連アルゴリズムの分析、Robert Sedgewick、第 4 回ヨーロッパアルゴリズムシンポジウム、バルセロナ、1996 年 9 月。

Wikibookアルゴリズム実装には、シェルソートに関するページがあります。

• アニメーションソートアルゴリズム: Wayback Machineの Shell Sort (2015 年 3 月 10 日アーカイブ) – グラフィカルなデモンストレーション
• ハンガリーの民族舞踊である、5、3、1の隙間があるシェルソート