クイックソートが他のクイックソートよりも平均的に速いのはなぜですか？

Question

私が知っているように、クイックソートのパフォーマンスは平均でO（n * log（n））ですが、マージとヒープソートのパフォーマンスは平均でもO（n * log（n））です。ですから、クイックソートが平均的に速いのはなぜでしょうか。

Answer 1

クイックソートの最悪ケースは、実際にはヒープソートとマージソートよりも悪いです。でもクイックソートは平均で速いです。同じ漸近のアルゴリズムに直面したとき

：なぜ、それを説明するには時間がかかりますので、私はSkiena, The algorithm design manual.

にマージ/ヒープソート対クイックソートをまとめた見積もりを参照するによう

複雑さ、実装 キャッシュのパフォーマンスやメモリサイズなどの詳細とシステムの傾向は、確かに決定的な要因であることが判明しているかもしれません。 実験では、適切に実装された クイックソートがうまく実装されている場合、通常、mergesortまたは ヒープソートより2〜3倍高速であることが実験からわかります。主な理由は、最も内側のループの操作が であることです。しかし、私がquicksortが であると言うとき、あなたが私を信じていなければ、私はあなたと議論することはできません。それは私たちが使用している分析ツールの外にある問題です。 伝える最も良い方法は、アルゴリズムと実験の両方を実装することです。

Answer 2

Wikipedia suggests：

その内部ループが 効率的に最も アーキテクチャ上で、最も現実世界で実現することができるので、典型的には、クイックソートは、他のO（nlogn） アルゴリズムよりも、実際にはかなり 高速であります データでは、二次的な時間を必要とする確率 を最小限に抑えるように設計することが可能です（ ）。 さらに、クイックソートは、 の仮想メモリと利用可能なキャッシュ の完全な利点を利用して、メモリの優れた使用方法を、 にする傾向があります。 quicksortは内部ではありません 補助メモリを並べ替えて使用しますが、 は最新のコンピュータ アーキテクチャに非常に適しています。

同じページにcomparison with other sorting algorithmsも見てください。

CSサイトのWhy is quicksort better than other sorting algorithms in practice?も参照してください。

Answer 3

Timsortは、一般に並べ替えの際に見られる種類のデータのために最適化されているので、データはしばしば埋め込まれた項目の「実行」を含むPython言語では、betterオプションです。最近はJavaにも採用されています。