問題タブ [quicksort]

面接でこんな質問をされました。どちらも O(nlogn) ですが、ほとんどの人は Mergesort の代わりに Quicksort を使用しています。何故ですか？

クイックソートを実装するとき、やらなければならないことの 1 つは、ピボットを選択することです。しかし、以下のような疑似コードを見ると、どのようにピボットを選択すればよいかが明確ではありません。リストの最初の要素? 他の何か？

ピボットを選択する概念と、異なるシナリオが異なる戦略を必要とするかどうかを理解するのを手伝ってくれる人はいますか?

昨日、クイックソートの実装に取り​​組んでいましたが、マージソート (これも実装しました) よりも実行時間が速いことを期待して実行しました。私は2つを実行しました.100要素未満の小さなデータセットではクイックソートの方が高速でしたが（動作することを確認しました）、マージソートはかなり迅速なアルゴリズムになりました. クイックソートはほとんどの場合、マージソートよりも「速い」と教えられていました。このトピックについてはいくつかの議論があることを理解していますが、少なくともこれよりも近いと予想していました。10000 要素を超えるデータ セットの場合、マージソートは 4 倍以上高速でした。これは予想されることですか、それともクイックソート コードにエラーがありますか?

マージソート:

クイックソート:

クイックソートのさまざまなバージョンをすべて説明するための完全な技術語彙を知っている人はいますか?

私が知っているのは「ファット ピボット」[A] (ピボットに一致するすべてのアイテムがサブ配列の中央に配置され、それ以上の並べ替えから除外される) です。

私が知りたいのは、1 つの要素 (ピボット) が中央に配置され、並べ替えから除外される場合 [B] と、中央にゼロ要素が配置される場合 [C] です。

これらのそれぞれの分割の例:
入力サブ配列は 5,3,2,9,5,7
[A] は [3,2],5,5,[ 9,7] を返します [
B]は [3,2] を返します],5,[9,5,7]
[C] は [3,2,5],[9,5,7] を与える

これが QuickSort の正しい実装であるかどうかを確認したいのですが、仕事をしているようですが、何か見逃していますか?

}

修繕：

クイックソートの最悪の場合のパフォーマンスは O(n ² ) ですが、実際にはまだ広く使用されています。どうしてこれなの？

List Sort メソッドがソートを処理する方法に問題があります。次の要素があるとします。

このように並べ替えようとすると、次のようになります。

次に、最初の要素は、前の 2 番目の要素「Second」です。または、言い換えると、このアサーションは失敗します。

要素が本質的に同じであるのに、.NET がリストを並べ替えるのはなぜですか? 比較でゼロ以外の値が返された場合にのみ、リストを並べ替えたいと思います。

3 ウェイ パーティションの QuickSort とは何ですか?