面接でこんな質問をされました。どちらも O(nlogn) ですが、ほとんどの人は Mergesort の代わりに Quicksort を使用しています。何故ですか？
Xardas
質問する
213363 次
29 に答える
313
クイックソートには、O( n 2 ) の最悪ケースのランタイムと O( n log n ) の平均ケースのランタイムがあります。ただし、多くのシナリオでは、多くの要因がアルゴリズムの実行時間に影響を与えるため、マージ ソートよりも優れています。
特に、よく引用される並べ替えアルゴリズムの実行時間は、データを並べ替えるために実行する必要がある比較の数またはスワップの数を指します。特に基礎となるハードウェア設計から独立しているため、これは確かにパフォーマンスの優れた尺度です。ただし、現在のハードウェアでは、参照の局所性 (つまり、おそらくキャッシュにある多くの要素を読み取るか) などの他の要素も重要な役割を果たします。特にクイックソートは追加のスペースをほとんど必要とせず、キャッシュの局所性が優れているため、多くの場合、マージソートよりも高速になります。
さらに、ピボットをランダムに選択するなど、ピボットの適切な選択を使用することで、O( n 2 )のクイックソートの最悪の場合の実行時間をほぼ完全に回避することは非常に簡単です (これは優れた戦略です)。
実際には、クイックソート (特に libstdc++ のstd::sort) の多くの最新の実装は実際にはintrosortであり、その理論上の最悪のケースは O( n log n ) であり、マージ ソートと同じです。再帰の深さを制限し、 log nを超えると別のアルゴリズム ( heapsort )に切り替えることでこれを実現します。
于 2008-09-16T09:14:24.870 に答える
302
多くの人が指摘しているように、クイックソートの平均的なケースのパフォーマンスは、マージソートよりも高速です。 ただし、これは、オンデマンドでメモリの一部にアクセスする時間が一定であると想定している場合にのみ当てはまります。
RAM では、この仮定は一般的にそれほど悪くはありません (キャッシュのために常に正しいとは限りませんが、それほど悪くはありません)。ただし、データ構造がディスク上に存在するのに十分な大きさである場合、平均的なディスクが 1 秒あたり 200 回のランダム シークを行うという事実によって、クイックソートは殺されます。しかし、その同じディスクでは、毎秒メガバイト単位のデータをシーケンシャルに読み書きするのに問題はありません。これはまさにmergesortが行うことです。
したがって、データをディスク上でソートする必要がある場合は、マージソートでいくつかのバリエーションを使用する必要があります。(通常、サブリストをクイックソートしてから、サイズのしきい値を超えてそれらをマージし始めます。)
さらに、そのサイズのデータセットを処理する必要がある場合は、ディスクへのシークを回避する方法をよく考えてください。たとえば、これが、データベースに大量のデータをロードする前にインデックスを削除し、後でインデックスを再構築するという標準的なアドバイスである理由です。ロード中にインデックスを維持するということは、常にディスクをシークすることを意味します。対照的に、インデックスを削除すると、データベースは最初に処理する情報を並べ替え (もちろんマージソートを使用)、次にそれをインデックスの BTREE データ構造にロードすることでインデックスを再構築できます。(BTREE は自然に順番に保持されるため、ディスクへのシークをほとんど行わずに、並べ替えられたデータセットから 1 つを読み込むことができます。)
ディスク シークを回避する方法を理解することで、データ処理ジョブに数日または数週間ではなく数時間かかるようになったことが何度もありました。
于 2008-09-18T06:19:50.607 に答える
96
実際、QuickSort は O(n 2 ) です。その平均実行時間は O(nlog(n)) ですが、最悪の場合は O(n 2 ) です。これは、一意の項目がほとんどないリストで実行したときに発生します。ランダム化には O(n) かかります。もちろん、これは最悪のケースを変えるものではなく、悪意のあるユーザーがソートに長時間かかるのを防いでいるだけです。
QuickSort は、次の理由で人気があります。
- インプレースです (MergeSort は、並べ替える要素の数に応じて追加のメモリを必要とします)。
- 小さな隠れ定数があります。
于 2008-09-16T08:41:02.123 に答える
34
「それでも、ほとんどの人はマージソートの代わりにクイックソートを使用しています。それはなぜですか?」
与えられていない心理的な理由の 1 つは、Quicksort の方が巧妙に命名されているということです。つまり、優れたマーケティングです。
はい、トリプル パーティショニングを使用したクイックソートはおそらく最良の汎用ソート アルゴリズムの 1 つですが、「クイック」ソートは「マージ」ソートよりもはるかに強力に聞こえるという事実を克服することはできません。
于 2009-11-13T04:53:23.077 に答える
21
他の人が指摘したように、クイックソートの最悪のケースは O(n^2) ですが、マージソートとヒープソートは O(nlogn) のままです。ただし、平均的なケースでは、3 つすべてが O(nlogn) です。したがって、それらはほとんどの場合に匹敵します。
クイックソートが平均的に優れているのは、内側のループが複数の値を単一の値と比較することを意味するのに対し、他の 2 つの条件は比較ごとに異なることです。つまり、Quicksort は、他の 2 つのアルゴリズムの半分の読み取りを行います。最新の CPU では、パフォーマンスはアクセス時間に大きく左右されるため、最終的にはクイックソートが優れた最初の選択肢になります。
于 2008-09-17T02:09:41.417 に答える
9
これまでに述べた 3 つのアルゴリズム (mergesort、quicksort、heap sort) のうち、mergesort のみが安定していることを追加したいと思います。つまり、同じキーを持つ値の順序は変わりません。場合によっては、これが望ましいこともあります。
しかし、実のところ、実際の状況では、ほとんどの人は平均的な優れたパフォーマンスしか必要とせず、クイックソートは... 迅速です =)
すべてのソートアルゴリズムには浮き沈みがあります。概要については、並べ替えアルゴリズムに関するウィキペディアの記事を参照してください。
于 2008-09-16T08:47:45.633 に答える
7
クイックソートは、別の再帰ソート アルゴリズムであるマージソートとも競合しますが、最悪の場合の Θ(nlogn) 実行時間という利点があります。マージソートは、クイックソートやヒープソートとは異なり、安定したソートであり、リンクされたリストや、ディスク ストレージやネットワーク接続ストレージなどのアクセスが遅いメディアに格納された非常に大きなリストの操作に簡単に適応できます。リンクされたリストで動作するようにクイックソートを作成することはできますが、ランダム アクセスがないと、ピボットの選択がうまくいかないことがよくあります。マージソートの主な欠点は、配列を操作する場合、最良の場合でも Θ(n) 補助スペースが必要になるのに対し、インプレース パーティショニングと末尾再帰を使用するクイックソートのバリアントは Θ(logn) スペースのみを使用することです。(リンクされたリストを操作する場合、mergesort は少量の一定量の補助記憶域しか必要としないことに注意してください。)
于 2008-09-16T08:42:10.967 に答える
7
ムー！ クイックソートは優れているわけではありません。マージソートよりも、別の種類のアプリケーションに適しています。
Mergesort は、速度が重要であり、最悪の場合のパフォーマンスの低下が許容されず、余分なスペースが利用できる場合に検討する価値があります。1
あなたは「彼らは両方とも O(nlogn) […]」であると述べました。これは間違っています。«Quicksort は、最悪の場合でも約 n^2/2 の比較を使用します。» 1 .
ただし、私の経験によると、最も重要なプロパティは、命令型パラダイムでプログラミング言語を使用するときにソート中に使用できる順次アクセスの簡単な実装です。
1セジウィック、アルゴリズム
于 2008-09-16T09:13:40.597 に答える
6
クイックソートは、実際には最も高速なソート アルゴリズムですが、O(n2) と同じくらいパフォーマンスが低下する病理学的ケースが多数あります。
ヒープソートは、O(n*ln(n)) で実行されることが保証されており、有限の追加ストレージしか必要としません。しかし、ヒープソートが平均してクイックソートよりも大幅に遅いことを示す実際のテストの多くの引用があります。
于 2008-09-16T08:41:30.220 に答える
4
マージ ソートとは異なり、クイック ソートは補助スペースを使用しません。一方、マージソートは補助スペース O(n) を使用します。ただし、マージソートの最悪の場合の時間の複雑さは O(nlogn) ですが、クイックソートの最悪の場合の複雑さは O(n^2) であり、配列が既にソートされている場合に発生します。
于 2016-08-26T06:56:18.957 に答える
4
クイックソートはマージソートより優れているわけではありません。O(n^2) (めったに起こらない最悪のケース) では、クイックソートはマージソートの O(nlogn) よりもはるかに遅くなる可能性があります。クイックソートはオーバーヘッドが少ないため、n が小さく低速のコンピューターでは優れています。しかし、今日のコンピューターは非常に高速であるため、マージソートによる追加のオーバーヘッドは無視できる程度であり、ほとんどの場合、非常に遅いクイックソートのリスクは、マージソートのわずかなオーバーヘッドをはるかに上回ります。
さらに、マージソートは、同一のキーを持つ項目を元の順序で残します。これは便利な属性です。
于 2008-09-16T22:29:46.080 に答える
4
これは、マージソートの最悪の場合のパフォーマンスが優れているにもかかわらず、特に大きな入力の場合、マージソートよりもクイックソートの方が優れていると見なされるというインタビューでよく聞かれる質問です。クイックソートの方が優れているという特定の理由があります。
1- 補助スペース:クイック ソートはインプレース ソート アルゴリズムです。インプレース ソートとは、ソートを実行するために追加のストレージ スペースが必要ないことを意味します。一方、マージソートでは、ソートされた配列をマージするために一時配列が必要なため、インプレースではありません。
2- 最悪のケース:クイックソートの最悪のケースは、O(n^2)ランダム化されたクイックソートを使用することで回避できます。適切なピボットを選択することで、高確率で簡単に回避できます。適切なピボット要素を選択して平均的なケースの動作を取得すると、パフォーマンスが即興になり、マージソートと同じくらい効率的になります。
3- 参照の局所性:特にクイックソートはキャッシュの局所性が優れているため、仮想メモリ環境などの多くの場合、マージ ソートよりも高速になります。
4- 末尾再帰: QuickSort は末尾再帰ですが、マージ ソートはそうではありません。末尾再帰関数は、再帰呼び出しが関数によって最後に実行される関数です。末尾再帰関数は、末尾再帰がコンパイラによって最適化される可能性があるため、非末尾再帰関数よりも優れていると見なされます。
于 2020-03-19T15:49:33.583 に答える
3
これはかなり古い質問ですが、最近両方を扱ったので、ここに私の2cがあります。
マージソートのニーズは平均で ~ N log N 回の比較です。すでに (ほぼ) ソート済みのソート済み配列の場合、これは 1/2 N log N に減少します。これは、マージ中に (ほぼ) 常に「左」部分を 1/2 N 回選択し、右に 1/2 N 要素をコピーするためです。さらに、既にソートされた入力がプロセッサの分岐予測子を輝かせると推測できますが、ほとんどすべての分岐を正しく推測し、パイプラインの停止を防ぎます。
クイック ソートには、平均で ~ 1.38 N log N の比較が必要です。比較に関しては、既に並べ替えられた配列から大きなメリットはありません (ただし、スワップに関しては、おそらく CPU 内の分岐予測に関してはそうです)。
かなり最新のプロセッサでの私のベンチマークは、次のことを示しています。
比較関数がコールバック関数の場合 (qsort() libc 実装のように)、クイックソートはマージソートよりランダム入力で 15%、64 ビット整数のソート済み配列で 30% 遅くなります。
一方、比較がコールバックでない場合、私の経験では、クイックソートはマージソートよりも最大 25% 優れています。
ただし、（大きな）配列に一意の値がほとんどない場合、マージソートはいずれにしてもクイックソートよりも優先され始めます。
要するに、比較にコストがかかる場合 (例: コールバック関数、文字列の比較、構造の多くの部分の比較は、違いを生むために 2 番目から 3 番目の "if" に到達することが多い) - 可能性としては、あなたの方が優れているということです。マージソートで。より単純なタスクでは、クイックソートの方が高速です。
前に言ったことはすべて真実です: - クイックソートは N^2 になる可能性がありますが、Sedgewick は、優れたランダム化された実装では、ソートを実行するコンピューターが N^2 になるよりも稲妻に打たれる可能性が高いと主張しています - マージソートには余分なスペースが必要です
于 2016-08-25T23:55:17.400 に答える
3
答えは、プリミティブ値に対して DualPivotQuickSort でもたらされた変更に対して、クイックソートに関してわずかに傾いています。Java 7でjava.util.Arraysでソートするために使用されます。
It is proved that for the Dual-Pivot Quicksort the average number of
comparisons is 2*n*ln(n), the average number of swaps is 0.8*n*ln(n),
whereas classical Quicksort algorithm has 2*n*ln(n) and 1*n*ln(n)
respectively. Full mathematical proof see in attached proof.txt
and proof_add.txt files. Theoretical results are also confirmed
by experimental counting of the operations.
ここでJAVA7の実装を見つけることができます - http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/util/Arrays.java
DualPivotQuickSort に関するさらに素晴らしい読み物 - http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628
于 2013-04-03T14:31:52.363 に答える
2
クイックソートはケースの平均複雑度が優れていますが、一部のアプリケーションでは間違った選択です。Quicksort は、サービス拒否攻撃に対して脆弱です。攻撃者がソートする入力を選択できる場合、攻撃者は、最悪の場合の時間の複雑さが o(n^2) になるセットを簡単に作成できます。
Mergesort の平均的なケースの複雑さと最悪のケースの複雑さは同じであるため、同じ問題は発生しません。マージソートのこの特性は、リアルタイムシステムの優れた選択肢にもなります。これは、実行が非常に遅くなるような病理学的なケースがないためです。
これらの理由から、私は Quicksort よりも Mergesort の方が好きです。
于 2008-09-16T08:42:05.273 に答える
2
MergeSort の最悪の結果は n(log2n)-n+1 であり、n が 2^k に等しい場合に正確です (これは既に証明済みです)。また、任意の n については、(n lg n - n + 1) と (n lg n + n + O(lg n))。ただし、クイックソートの場合、nlog2n が最適です (n は 2^k に等しい)。マージソートをクイックソートで割ると、n が無限大の場合に 1 になります。 MergeSort の最悪のケースが QuickSort の最良のケースよりも優れているかのように、なぜクイックソートを使用するのでしょうか?しかし、覚えておいてください、MergeSort は適切に配置されておらず、2n メモリ スペースが必要です。アルゴリズムの分析には含めないでください。一言で言えば、MergeSortは理論的にはクイックソートよりも高速ですが、実際にはメモリスペースを考慮する必要があり、配列のコピーのコスト、マージはクイックソートよりも遅くなります。ランダムクラスによってJavaで1000000桁が与えられた実験、マージソートで2610ミリ秒、クイックソートで1370ミリ秒かかりました。
于 2011-09-10T15:33:06.913 に答える
2
両方の並べ替えアルゴリズムを試してみたところ、再帰呼び出しの数を数えることによって、クイックソートは一貫してマージソートよりも再帰呼び出しが少なくなりました。これは、クイックソートにピボットがあり、ピボットが次の再帰呼び出しに含まれていないためです。そうすれば、クイックソートはマージソートよりも速く再帰的な基本ケースに到達できます。
于 2017-02-12T01:49:13.710 に答える
1
どちらも同じ複雑さのクラスに属していますが、それは両方が同じランタイムを持っているという意味ではありません。クイックソートは通常、マージソートよりも高速です。これは、厳密な実装をコーディングする方が簡単で、実行する操作が高速になるためです。人々がマージソートの代わりにクイックソートを使用するのは、一般的に高速だからです。
でも！私は個人的に、クイックソートがうまくいかないときにマージソートまたはマージソートに劣化するクイックソートバリアントをよく使用します。覚えて。クイックソートは平均で O(n log n) しかありません。最悪の場合は O(n^2) です! マージソートは常に O(n log n) です。リアルタイムのパフォーマンスまたは応答性が必須であり、入力データが悪意のあるソースから来ている可能性がある場合は、プレーンなクイックソートを使用しないでください。
于 2008-09-16T08:44:17.437 に答える
1
すべてが同じであれば、ほとんどの人は最も便利に利用できるものを使用すると思いますが、それは qsort(3) である傾向があります。それ以外では、マージソートがリストの一般的な選択であるように、配列ではクイックソートが非常に高速であることが知られています。
私が疑問に思っているのは、基数やバケットの並べ替えがほとんど見られない理由です。それらは、少なくともリンクされたリストでは O(n) であり、必要なのはキーを序数に変換する何らかの方法です。(文字列とフロートは問題なく動作します。)
その理由は、コンピュータ サイエンスの教育方法に関係していると思います。アルゴリズム分析の講師に、実際に O(n log(n)) よりも高速にソートできることを示す必要さえありました。(彼は、 O(n log(n)) よりも速く比較ソートできないことを証明しました。これは本当です。)
他のニュースでは、フロートは整数としてソートできますが、後で負の数を元に戻す必要があります。
編集: 実際には、フロートを整数としてソートするさらに悪質な方法があります: http://www.stereopsis.com/radix.html。実際に使用するソートアルゴリズムに関係なく、ビットフリッピングのトリックを使用できることに注意してください...
于 2008-09-28T00:45:48.963 に答える
-1
c/c++ の世界では、stl コンテナーを使用しない場合、ランタイムに組み込まれているため、クイックソートを使用する傾向がありますが、マージソートはそうではありません。
ですから、多くの場合、それが最も抵抗の少ない道であると私は信じています。
さらに、データセット全体がワーキング セットに収まらない場合は、クイック ソートを使用するとパフォーマンスが大幅に向上します。
于 2008-09-17T02:00:10.113 に答える