問題タブ [shellsort]

C#を使用してシェルソートを行うより良い方法はありますか?

ちなみに、さまざまな言語で「エレガントな」並べ替えの例がいくつかあるので ( C#とF#のバブル ソートなど)、それらを比較しています。実生活では、C# でほとんどの場合、次のコードを使用します。

これらが「学術的」で非実用的なパターンであるかどうかは気にしません。必要に応じて、私をオブリビオンにダウンモッドできます:)

カ

Marcin Ciura の最適な (最もよく知られている) シェル ソート アルゴリズムのインクリメント シーケンスによると、シェル ソートの最適なシーケンスは 1、4、10、23、57、132、301、701 ... ですが、そのようなシーケンスを生成するにはどうすればよいですか? Marcin Ciura の論文で、彼は次のように述べています。

クヌースとヒバードの数列はどちらも、単純な線形回帰によって定義されているため、比較的悪いものです。

しかし、私が見つけたほとんどのアルゴリズムの本は、Knuth の数列を使用する傾向があります。k = 3k + 1 は、生成が簡単なためです。シェルソートシーケンスを生成する方法は何ですか?

C# で ShellSort を使用して配列を並べ替える簡単な方法が必要です。助けてください

シェルソートの例を教えてもらえますか？私はここでシェルソートについて学ばなければならない新しい人ですが、最初にJavaシェルソートの例を見つけなければなりません。Googleで1つの例を見つけましたが、それは難しすぎます。

このコードを変更して、このコードの代わりに Knuth の H シーケンスを使用できるようにしたいと考えています。誰かが助けてくれれば、とても感謝しています。

標準の間隔サイズを使用している場合と、非標準のサイズを使用している場合のシェルソートの効率をテストする必要があります。私が遭遇している問題は、非標準の間隔を使用しようとしたときです。

これは、h が標準間隔サイズに等しい場合の私の Shellsort です。

そして、これが素数間隔を使用する私の試みです

リアルタイム効率に基づいて 2 つを比較しようとしていますが、このプリム間隔を機能させる方法がわかりません。

私はテストしようとしています:

• Shellsort は、適切に選択された間隔サイズで O(N^2) よりも優れたパフォーマンスを発揮します
• 選択された一連の間隔サイズは、O(N^2) ランタイムよりも優れたものを達成するために重要です

助けてくれてありがとう。

openmp に詳しい人はいますか? 並べ替えられたリストを取得できません。私は何を間違っていますか。最後にクリティカルを使用しているため、ソートされたときにそのセクションにアクセスできるのは1つのスレッドだけです。私の個人的な価値観は正しくないと思います。それらが存在する必要があるのか​​、それとも #pragma omp for だけでよいのでしょうか。

以下のように、シェルソートアルゴリズムの分析について言及されているアルゴリズムに関する本を読んでいます。

Shell のインクリメントを使用した、Shellsort の最悪の場合の実行時間は、Theta(n 平方) です。

この証明には、最悪の場合の実行時間の上限を示すだけでなく、実行に Omeaga(n 平方) 時間として実際に下限を取る何らかの入力が存在することを示す必要があります。悪いケースを構築することにより、最初に下限を証明します。

上記の私の質問は次のとおりです。

1. なぜ著者は下限をチェックするために悪いケースに言及しているのですか? 下限を取得するように教えましたが、最善のケースを採用する必要があります。上記を明確にするようお願いします。

ありがとう！

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

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

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

ありがとう！

わかりました、これはデータ構造クラス用です。割り当ては、txt ファイルから 100 個の整数のリストを取得し、シェル ソート用に 4 つの間隔の 2 つの異なるセットを取得し、100 個の数値を 1) 挿入ソートで、2) 最初のシェル ソートでソートするプログラムを作成することでした。間隔として 4 つの数字、3) 間隔として 100 秒ごとにシェル ソートし、ソートされたリストを txt ファイルに出力し、各ソートで行われた割り当て操作の量を出力します (この部分はまだ行っていません)。

シェルソートの 1 つをコンパイルして実行すると、部分的にソートされていますが、通常は完全には機能しません。完全にソートされないシェルソートはどちらかのソートである可能性があるため、プログラムは特定の間隔で動作し、他の間隔では動作しないと想定しています:)。誰でも助けてくれますか