Marcin Ciura の最適な (最もよく知られている) シェル ソート アルゴリズムのインクリメント シーケンスによると、シェル ソートの最適なシーケンスは 1、4、10、23、57、132、301、701 ... ですが、そのようなシーケンスを生成するにはどうすればよいですか? Marcin Ciura の論文で、彼は次のように述べています。
クヌースとヒバードの数列はどちらも、単純な線形回帰によって定義されているため、比較的悪いものです。
しかし、私が見つけたほとんどのアルゴリズムの本は、Knuth の数列を使用する傾向があります。k = 3k + 1 は、生成が簡単なためです。シェルソートシーケンスを生成する方法は何ですか?
Ciura の論文では、一連のシーケンスが経験的に生成されています。つまり、彼は多くの組み合わせを試しましたが、これが最も効果的でした。最適なシェルソート シーケンスを生成することは難しいことが判明しており、これまでのところ、この問題は分析に耐えられませんでした。
最もよく知られているインクリメントは Sedgewick のもので、ここで読むことができます(p. 7 を参照)。
データ セットのサイズに明確な上限がある場合は、ステップ シーケンスをハードコーディングできます。データセットが上限なしで大きくなる可能性が高い場合は、おそらく一般性についてのみ心配する必要があります。
示されているシーケンスは、癖はありますが、おおまかに指数系列として成長しているようです。素数の大部分があるようですが、素数以外の数も混在しています。明らかな生成式がわかりません。
任意に大きなセットを処理する必要があると仮定すると、最悪の場合のパフォーマンス、平均的な場合のパフォーマンス、またはほぼソートされたパフォーマンスを強調する必要があるかどうかという有効な質問があります。後者の場合、挿入ステップで二分探索を使用する単純な挿入ソートの方が、シェルソートよりも優れている場合があります。最悪の場合のパフォーマンスが必要な場合は、セッジウィックのシーケンスが好まれるようです。あなたが言及したシーケンスは、比較の数が移動の数を上回る平均的なケースのパフォーマンス向けに最適化されています。
ウィキペディアのシェルソートの記事にあるアドバイスを恥ずかしがらずに受け入れます。
比較の平均数に関して、最もよく知られているギャップ シーケンスは、1、4、10、23、57、132、301、701 などであり、ギャップは実験的に発見されています。701 を超える最適なギャップは不明のままですが、再帰式 h_k = \lfloor 2.25 h_{k-1} \rfloor に従って上記のシーケンスを拡張することにより、良好な結果を得ることができます。
徳田の数列 [1, 4, 9, 20, 46, 103, ...] は、単純な式 h_k = \lceil h'_k \rceil で定義されます。ここで、h'k = 2.25h'k − 1 + 1, h '1 = 1、実用的なアプリケーションに推奨できます。
仮名から推測すると、Marcin Ciura が WP の記事を自分で編集したようです。
シーケンスは 1、4、10、23、57、132、301、701、1750 です。1750 の後の次の数値ごとに、前の数値に 2.25 を掛けて切り捨てます。
昨日、特定の (低い) n が与えられた場合に最も効果的であることがわかったギャップ シーケンスを含めて、この質問についてここで説明しました。
途中で書きます
シェルソートの厄介な副作用は、(処理/評価時間を節約するために) n 個のエントリのランダムな組み合わせのセットを使用してギャップをテストする場合、n 個のエントリに最適なギャップ、または一連のエントリに最適なギャップのいずれかになる可能性があることです。組み合わせ - おそらく後者です。
問題は、有効な結論を引き出すことができるように、提案されたギャップをテストすることにあります。明らかに、すべての n に対してギャップをテストします! n個の一意の値のセットを表現できる順序付けは実行不可能です。たとえば、n=16 についてこの方法でテストすると、正確な平均、最悪、および逆に並べ替えられたケースを決定するために、n 値の 20,922,789,888,000 の異なる組み合わせを並べ替える必要があることを意味します。一番。n=16 の場合、2^(16-2) セットのギャップが可能です。最初は {1}、最後の {15,14,13,12,11,10,9,8,7,6,5,4 ,3,2,1}。
ランダムな組み合わせを使用すると誤った結果が得られる可能性があることを説明するために、n=3 と仮定すると、012、021、102、120、201、および 210 の 6 つの異なる順序を想定できます。2 つのランダム シーケンスのセットを生成して、2 つの可能なギャップ セット {1 }および{2,1}。これらのシーケンスが 021 と 201 であることが判明したと仮定します。{1} の場合、021 は 3 つの比較 (02、21、および 01) でソートでき、201 は (20、21、01) で合計 6 つの比較が得られ、2 で除算できます。ほら、平均は 3 で、最悪の場合は 3 です。{2,1} を使用すると、021 の場合は (01、02、21、および 01)、201 の場合は (21、10、および 12) が得られます。 4、平均3.5。{1] の実際の平均と最悪のケースは、それぞれ 8/3 と 3 です。{2,1} の場合、値は 10/3 と 4 です。両方のケースで平均が高すぎ、最悪のケースが正しかったです。
これを拡張して、n=16 のランダム シーケンスのセットを見つけ、テストされたギャップのセットが他のものと比較して優先されず、結果が真の値に近い (または等しい) ようにし、処理を最小限に抑えます。 . それはできますか？おそらく。結局のところ、すべてが可能ですが、可能性はありますか? この問題では、ランダムは間違ったアプローチだと思います。いくつかのシステムに従ってシーケンスを選択することは、それほど悪くないかもしれませんし、良いかもしれません.