algorithm - シェルソートと挿入ソート

Question

問題が発生しました。シェルソートと挿入ソートアルゴリズムについて非常に混乱しています。どのように区別すればよいでしょうか？

Answer 1

シェル ソートは、挿入ソートの一般化されたバージョンです。基本的な原理は、両方のアルゴリズムで同じです。長さnの並べ替えられたシーケンスがあり、それに並べ替えられていない要素を挿入すると、n+1要素の長さの並べ替えられたシーケンスが得られます。

違いは次のとおりです。一方、挿入ソートは 1 つのシーケンス (最初は配列の最初の要素) でのみ機能し、それを (次の要素を使用して) 展開します。ただし、シェル ソートではインクリメントが減少します。つまり、比較される要素間にギャップがあります (最初はn/2 )。したがって、挿入ソートを使用してソートされるn/2シーケンスがあります。各ステップで増分が縮小され (多くの場合2.2で割られるだけ)、シーケンスの数が減少します。最後のステップではギャップはなく、アルゴリズムは単純な挿入ソートに退化します。

増分が減少するため、大きな要素と小さな要素が迅速に移動されて配列の一部が修正され、挿入ソートを使用してソートされた最後のステップよりも非常に高速になります。これにより、時間の複雑さが軽減されますO(n^(4/3))

Answer 2

連続する要素の一連の比較とスワップとして、挿入ソートを実装できます。それが「安定ソート」になります。代わりに、シェルソートは、互いに離れている要素を比較して交換します。それはそれをより速くします。

あなたの混乱は、データの異なるサブセットに適用されるいくつかの挿入ソートとしてシェルソートを実装できるという事実から来ていると思います。これらのサブセットは、データ シーケンスの連続しない要素で構成されていることに注意してください。

詳細についてはウィキペディアを参照してください;-)

Answer 3

挿入ソートは、単純なインプレース O(N^2) ソートです。シェルソートはもう少し複雑で理解しにくく、O(N^(5/4)) あたりのどこかです。例については、リンクを参照してください。違いは簡単にわかるはずです。