algorithm - シェルソートアルゴリズムについて

Question

アルゴリズムに関する本を読んでいます。シェルソートでは以下のように記載されています

シェルソートの重要な特性（証明なしで述べています）は、（h subscipt k）hk-sortedファイルが（h subsciprt（k-1））hk-1-sortedのままであるということです。そうでない場合、初期段階で行われた作業は後の段階で取り消されるため、アルゴリズムはほとんど価値がない可能性があります。

私の質問は、著者が上記のステートメントとはどういう意味ですか？

ありがとう！

Answer 1

シェルソートは、マルチパスソートアルゴリズムです。これは、配列のサブセットを特定の整数の「ストライド」値でソートすることによって機能します。つまり、配列内のすべての要素にkのみアクセスします。kth

最初はストライドに大きな値が使用されますが、後続のパスでは、このストライド値は、最後のパスがストライド1（通常は単なる標準の挿入ソートフェーズ）で実行され、配列が完全にソートされるまで減少します。

あなたが尋ねたステートメントは、以前のパス（より大きなストライド値）で行われたソートは、後のパス（より小さなストライド値）によって保持されることを単に示しています。そうでない場合、シェルソートで使用されるマルチパスアプローチには意味がありません。

お役に立てれば。