9

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

4

8 に答える 8

7

QuickSort の平均的な漸近順序は でO(nlogn)あり、定数が小さい (よりタイトなループ) ため、通常はヒープソートよりも効率的です。実際、常に最適なピボットを見つけるために使用できる理論的な線形時間中央値選択アルゴリズムがあり、最悪のケースが発生しO(nlogn)ます。ただし、通常の QuickSort は通常、この理論上のものよりも高速です。

より賢明にするために、QuickSort が で終了する確率を考慮してください。つまり、その悪いケースに遭遇することはほとんどありません。O(n2)1/n!

于 2009-04-21T09:57:09.680 に答える
6

興味深いことに、クイックソートはマージソートよりも平均してより多くの比較を実行します。クイックソートの場合は 1.44 n lg n (予想)、マージソートの場合は n lg n です。重要なのは比較だけである場合、マージソートはクイックソートよりもはるかに望ましいでしょう。

クイックソートが高速である理由は、最新のハードウェアで非常にうまく機能する他の多くの望ましいプロパティがあるためです。たとえば、クイックソートには動的割り当ては必要ありません。再帰に必要なスタック フレームを格納するために、O(log n) スタック スペース (正しく実装されていれば最悪の場合) のみを使用して、元の配列のインプレースで動作できます。マージソートを使用してこれを行うことはできますが、通常、これを行うと、マージ ステップ中にパフォーマンスが大幅に低下します。ヒープソートなどの他のソート アルゴリズムにも、このプロパティがあります。

さらに、クイックソートには優れた参照局所性があります。Hoare のインプレース パーティショニング アルゴリズムを使用して行う場合、パーティショニング ステップは、基本的に、アレイの両端から内側に向​​かって実行される 2 つの線形スキャンです。これは、クイックソートのキャッシュ ミスが非常に少ないことを意味します。これは、最新のアーキテクチャではパフォーマンスにとって重要です。一方、ほとんどのマージソート実装には適度な局所性がありますが、ヒープソートにはあまり優れた局所性がありません (配列全体をジャンプします)。

クイックソートも非常に並列化可能です。配列をより小さな領域とより大きな領域に分割する最初の分割ステップが発生すると、それらの 2 つの部分を互いに独立して並べ替えることができます。マージソートを含む多くのソートアルゴリズムは並列化できますが、上記の理由により、並列クイックソートのパフォーマンスは他の並列アルゴリズムよりも優れている傾向があります。一方、ヒープソートはそうではありません。

クイックソートの唯一の問題は、O(n 2 ) に劣化する可能性があることです。これは、大規模なデータ セットでは非常に深刻になる可能性があります。これを回避する 1 つの方法は、アルゴリズムをそれ自体でイントロスペクトし、劣化した場合に低速だがより信頼性の高いアルゴリズムの 1 つに切り替えることです。introsortと呼ばれるこのアルゴリズムは、異常なケースなしでクイックソートの多くの利点を得る優れたハイブリッド ソート アルゴリズムです。

要約すれば：

  • O(log n) スペースを使用する再帰で使用されるスタック フレームを除いて、クイックソートはインプレースです。
  • クイックソートには、参照の局所性があります。
  • クイックソートは簡単に並列化できます。

これは、紙の上では優れているかもしれないソートアルゴリズムよりもクイックソートの方がパフォーマンスが優れている理由を説明しています。

お役に立てれば！

于 2013-01-15T23:48:12.277 に答える
1

ただし、最速であることに加えて、並べ替えの前に配列をシャッフルすることで、いくつかの悪いケースのシナリオを回避できます。小さなデータセットの弱点については、データセットが小さく、ソート時間がおそらく小さいため、それほど大きな問題ではないことは明らかです。

例として、QuickSort とバブル ソート用の Python 関数を作成しました。バブル ソートでは、10,000 レコードをソートするのに約 20 秒、7500 レコードで 11 秒、5000 レコードで 5 秒かかります。クイックソートでは、これらすべてのソートを約 0.15 秒で実行します。

于 2013-01-15T21:38:37.420 に答える
1

平均して、(経過時間に関して) 最速の比較ソートであるためです。

于 2009-04-21T09:56:44.017 に答える
1

一般的なケースでは、これは最速のソート アルゴリズムの 1 つだからです。

于 2009-04-21T09:56:55.670 に答える
0

Bcsこれは、O（NlogN）の複雑さを持つ大規模なデータセットでうまく機能するアルゴリズムの1つです。これは、一定のスペースをとるインプレースアルゴリズムでもあります。ピボット要素を賢く選択することで、クイックソートの最悪のケースを回避でき、ソートされた配列でも常にO（NlogN）で実行されます。

于 2013-01-20T11:33:37.917 に答える