データセットがソート順またはほぼソート順である場合、パフォーマンスがひどく低下することは、クイックソートのよく知られた問題です。この場合、通常は非常に遅い挿入ソートが簡単に最良の選択です。問題は、いつどちらを使用するかを知ることです。
データセットを実行し、比較係数を適用し、データセットが並べ替え順序にどれだけ近いかについてのレポートを返すために使用できるアルゴリズムはありますか？私はDelphi/Pascalが好きですが、例がそれほど複雑でなければ、他の言語を読むことができます。
2205 次
8 に答える
10
ご想像のとおり、これにはかなり多くの考えが入ります。3 の中央値手法は、並べ替えられたデータに対してはクイックソートの最悪のケースの動作が発生しないことを意味しますが、代わりにあまり明白でないケースに対して発生します。
イントロソートは、クイックソートの二次的な最悪のケースを完全に回避するため、非常にエキサイティングです。「データがほぼソートされていることをどのように検出するか」という自然な質問の代わりに、実際には、「これには時間がかかりすぎていますか?」と自問します。答えが「はい」の場合、クイックソートからヒープソートに切り替わります。
Timsortは、マージ ソートと挿入ソートを組み合わせたもので、ソート済みまたはリバース ソート済みのデータ、およびソート済みまたはリバース ソート済みのサブセットを含むデータに対して非常に優れたパフォーマンスを発揮します。
したがって、おそらくあなたの質問に対する答えは、「プレパス分析は必要ありません。適応ソートアルゴリズムが必要です」です。
于 2009-12-04T20:49:42.977 に答える
3
SmoothSortもあります。これは、実装が非常に難しいようですが、データの並べ替え方法に応じて、O（N log N）からO（N）の間で異なります。
http://en.wikipedia.org/wiki/Smoothsort
長くトリッキーなPDF： http ://www.cs.utexas.edu/users/EWD/ewd07xx/EWD796a.PDF
ただし、データが本当に巨大で、シリアルにアクセスする必要がある場合は、マージソートがおそらく最適です。これは常にO（N log N）であり、優れた「局所性」特性を備えています。
于 2009-12-04T20:14:25.110 に答える
0
考えられる解決策の1つは、現在の並べ替え範囲の最初、最後、および中央の要素を（QuickSort操作中に）取得し、中央の要素をピボット要素として選択することです。
于 2009-12-04T20:13:27.080 に答える
0
使用するアルゴリズムを決定する目的で完全に分析するには、ほぼソート作業を行います。ランダムではあるが増加するインデックスの小さな割合で値をチェックするようなことを行うことができます（つまり、アイテムの小さなサンプルを分析します）。
于 2009-12-04T20:13:35.847 に答える
0
QuickSort は、データ セットが巨大で、ほとんどが既に並べ替えられている場合にのみ問題を引き起こします。
データ セットのサイズがしきい値を下回っていても気にしないでください。
レコード (アイテム) への (インデックス化された) クイック アクセスがある場合は、N レコードごとに 1 レコードのサンプルを取得し、それらが既に並べ替えられているかどうかを確認します。小さなサンプルには十分な速さである必要があり、クイックソートを使用するかどうかを決定できます。
于 2009-12-04T20:48:48.343 に答える
0
並べ替え前の分析については聞いたことがありませんが、データセットを分析するためにデータセットを調べようとすると、全体的な並べ替え時間のパフォーマンスが既に低下しているというのが私の意見です。
于 2009-12-04T20:07:22.173 に答える
0
人々がまだ行っていない概念的な点を説明すると、クイックソートは常識的な分割統治アルゴリズムであり、まれに明らかなバグがあります。生徒の書類の束を並べ替えたいとします。(これには何らかの規則性が必要です。) クイックソート アルゴリズムでは、ピボットと呼ばれる用紙を選択します。次に、ピボットの前か後かに応じて、他の用紙を分割します。次に、2 つのサブパイルでそれを繰り返します。バグは何ですか？ピボットは、リストの中央ではなく、一方の端に近い名前にすることができます。そのため、2 つの山に分割してもあまり効果がありません。
マージ ソートは、別の順序で機能する別の分割統治アルゴリズムです。並べ替えられた 2 つのリストを線形時間でマージできます。論文を 2 つの同等またはほぼ同等の山に分割し、それぞれを再帰的に並べ替えてからマージします。マージソートにはバグがありません。クイックソートがマージソートよりも人気がある理由の 1 つは、歴史的なものです。クイックソートは (通常は) 高速であり、追加のメモリなしで動作します。しかし、最近では、メモリを節約することよりも比較を保存することが重要になる可能性があり、実際の再配置はポインターの並べ替えによって抽象化されることがよくあります。物事がいつもそうであったなら、マージソートはクイックソートよりも単純に人気があったのではないかと思います. （そして、名前に「クイック」を追加することは、良いセールスマンシップだったのかもしれません。）
于 2009-12-06T23:00:29.220 に答える
0
ソートされているかどうかを判断するためにすべてのレコードを実行する必要があるため、パフォーマンスを向上させるには、最初のレコードから始めて、正しくソートされていないことに気付くか、リストの最後に到達するまで残りを実行します。ミスが見つかった場合は、その位置から最後までの項目のみを並べ替えます (リストの先頭は既に並べ替えられているため)。
2 番目の部分の各項目で、項目が最初の部分の最後の要素よりも < であるかどうかを確認し、そうであれば最初の部分のみに挿入ソートを使用します。それ以外の場合は、2 番目の部分の他のすべてのアイテムに対してクイックソートします。このようにして、特定のケースに合わせて並べ替えが最適化されます。
于 2009-12-04T20:38:25.930 に答える