3

まず、この質問を投稿する前に検索を行いました。なぜクイックソートはマージソートよりも優れているのですか?の質問を見てきました。しかし、いくつかの矛盾した答えがあります。

私が見る場所によっては、参照の局所性、キャッシュヒットなどにより、クイックソートはマージソートよりも「速い」と言う人がいます。これは実際には重要であることを受け入れますが、私の質問は純粋に分析に関するものです-再帰には興味がありませんオーバーヘッド、キャッシュの問題など。さらに、答えは、より速く言ったときの意味が曖昧であることが多く、実行にかかる時間について言及しているかどうか、キャッシュの問題が答えに関連しているかどうかはわかりません。

とにかく、私の質問は簡単です。純粋に実行される比較の数に関して、マージソートは常にクイックソートよりも効率的ですか? ウィキペディアは、私がずっとそう思ってきたことですが、私が言ったように、他の人は別のことを言っています。

4

1 に答える 1

3

基本的なクイックソートは、最悪の場合、O(n^2) 時間で実行されます。選択されたピボットが常に次に小さい要素である場合、これは挿入ソートと同等です。Mergesort にはこの問題はありません。

さらに、Mergesort も安定しています。つまり、同じ値の要素の順序が保持されます (したがって、「最初にこれで、次にそれで」ソートするのに適しています)。Quicksort はそうではありません。

Mergesort の最大の欠点は、ほとんどの実装は 2n スペースで実行する必要があることですが、Quicksort はインプレースで実行できます (アプリケーションでスペースが問題になる場合)。

QuicksortMergesortの両方に関する個々のウィキペディアは優れているので、それらを読むことをお勧めします。

于 2012-10-27T02:31:55.943 に答える