QuickSortが実際に他のソートアルゴリズムよりも優れているのはなぜですか？

https://cs.stackexchange.com/questions/3

15-10-2019
|

質問

標準的なアルゴリズムコースでは、それを教えられます QuickSort 最悪の場合は$ o（n log n）$、$ o（n^2）$です。同時に、最悪の場合は$ o（n log n）$である他のソートアルゴリズムが研究されています（ mergesort と heapsort）、そして最高の場合の線形時間でさえ（ バブルソート）しかし、メモリの追加のニーズがあります。

一目見た後もう少し実行時間そのQuickSortと言うのは自然です いけない 他の人と同じくらい効率的になります。

また、学生は基本的なプログラミングコースで、再帰は一般的には良くないことを学ぶことを考えてみてください。再帰的なアルゴリズムであるため、本当に良いです。

それでは、なぜクイックソートは実際に他のソートアルゴリズムを上回るのでしょうか？ の構造に関係していますか 実際のデータ？コンピューターでのメモリの仕組みに関係していますか？いくつかの記憶は他の記憶よりもはるかに速いことを知っていますが、それがこのカウンターに反するパフォーマンスの本当の理由であるかどうかはわかりません（理論的推定と比較して）。

更新1： 標準的な答えは、平均ケースの$ o（n log n）$に関与する定数は、他の$ o（n log n）$ algorithmsに関与する定数よりも小さいことを言っています。ただし、直感的なアイデアのみではなく、正確な計算を使用して、これを適切に正当化することはまだありません。

いずれにせよ、いくつかの回答が示唆するように、メモリレベルでいくつかの回答が示唆するように、実装がコンピューターの内部構造を利用して、たとえばキャッシュメモリがRAMよりも速くなることを使用して、実際の違いが発生するようです。議論はすでに興味深いものですが、メモリ管理に関する詳細を確認したいと思います。答えはそれに関係しています。

更新2： ソートアルゴリズムの比較を提供するいくつかのWebページがあります。 sorting-algorithms.com）。素敵な視覚援助を提示する以外に、このアプローチは私の質問に答えません。

解決

短い答え

キャッシュ効率の引数はすでに詳細に説明されています。さらに、QuickSortが速い理由は本質的な議論があります。 2つの「交差ポインター」と同じように実装されている場合、たとえば、ここ, 、内側のループは非常に小さなボディを持っています。これは最も頻繁に実行されるコードであるため、これは報われます。

長い答え

初めに、

平均的なケースは存在しません！

実際には極端な場合が多いことが多いため、平均的なケース分析が行われます。しかし、平均的な症例分析はいくつかを想定しています 入力の分布！並べ替えの場合、典型的な選択はです ランダム順列モデル （ウィキペディアで暗黙のうちに想定されています）。

なぜ$ o $ notation？

アルゴリズムの分析における定数の破棄は、1つの主な理由で行われます：私が興味を持っている場合 ちょうど 実行時間、 関係するすべての基本操作の（相対的な）コストが必要です （まだキャッシュの問題を無視したり、最新のプロセッサでのパイプラインを無視したりします...）。数学的分析はできます カウント 各命令が実行される頻度ですが、単一命令の実行時間はプロセッサの詳細に依存します。たとえば、32ビットの整数の乗算に追加の時間がかかるかどうか。

2つの方法があります。

いくつかのマシンモデルを修正します。

これはドンで行われます クヌースの本シリーズ「コンピュータープログラミングの芸術」著者によって発明された人工的な「典型的な」コンピューターの場合。第3巻では、正確にわかります 平均ケース結果 多くのソートアルゴリズムについては、例：
- Quicksort：$ 11.667（n+1） ln（n）-1.74n-18.74 $
- mergesort：$ 12.5 n ln（n）$
- Heapsort：$ 16 N ln（n） +0.01n $
- insertionsort：$ 2.25N^2+7.75n-3ln（n）$
  ^[ソース]
これらの結果は、クイックソートが最速であることを示しています。しかし、それはKnuthの人工機械でのみ証明されているため、必ずしもあなたのx86 PCと言うことを意味するものではありません。また、アルゴリズムは小さな入力について異なる方法で関連することに注意してください。

^[ソース]
要約を分析します 基本操作.

比較ベースのソートについては、これは通常です スワップ と 重要な比較. 。ロバート・セッジウィックの本、例えば「アルゴリズム」, 、このアプローチが追求されています。あなたはそこにあります
- QuickSort：$ 2N ln（n）$比較と$ frac13n ln（n）$平均スワップ
- Mergesort：$ 1.44n ln（n）$比較ですが、最大$ 8.66n ln（n）$ arrayアクセス（Mergesortはスワップベースではないため、カウントできません）。
- insertionsort：$ frac14n^2 $比較と$ frac14n^2 $スワップは平均してスワップします。
ご覧のとおり、これは正確なランタイム分析としてアルゴリズムの比較を容易に許可するものではありませんが、結果は機械の詳細から独立しています。

その他の入力分布

上記のように、平均的なケースは常に何らかの入力分布に関してあるため、ランダムな順列以外のケースを考慮するかもしれません。たとえば、研究が行われました等しい要素を持つクイックソートそして、には素晴らしい記事があります Javaの標準ソート機能

他のヒント

この質問に関しては、複数のポイントを作成できます。

クイックソートは通常高速です

Quicksortには最悪の場合は$ o（n^2）$の動作がありますが、通常は高速です。ランダムなピボット選択を想定すると、入力を2つの同様のサイズのサブセットに分離するいくつかの数値を選択する可能性が非常に大きくなります。ほしい。

特に、10個のスプリットごとに10％〜90％の分割（MEHスプリット）を作成するピボットを選択し、1つの要素-$ n-1 $要素の分割（これは最悪の分割です。取得）、実行時間はまだ$ o（n log n）$です（これにより、定数が融合しているのはおそらく速いポイントに吹き飛ばされることに注意してください）。

クイックソートは通常、ほとんどの種類よりも高速です

クイックソートは通常、$ o（n log n）$（たとえば、$ o（n^2）$実行時間で挿入ソート）よりも遅いソートよりも速いです。

QuickSortが実際に非常に高速である理由は、Heapsortなどの他のほとんどの$ O（n log n）$アルゴリズムと比較して、比較的キャッシュ効率が高いためです。その実行時間は、実際には$ o（ frac {n} {b} log（ frac {n} {b}））$です。ここで、$ b $はブロックサイズです。一方、Heapsortはそのようなスピードアップを持っていません。メモリキャッシュ効率にまったくアクセスしていません。

このキャッシュ効率の理由は、入力を線形にスキャンし、入力を線形に分割するためです。これは、そのキャッシュを他のキャッシュに交換する前に、キャッシュにロードするすべての数値を読み取るときに、私たちが行うすべてのキャッシュ負荷を最大限に活用できることを意味します。特に、アルゴリズムはキャッシュブラビアスであり、キャッシュレベルごとに優れたキャッシュパフォーマンスを提供します。これは別の勝利です。

キャッシュ効率はさらに$ o（ frac {n} {b} log _ { frac {m} {b}}（ frac {n} {b}））にさらに改善できます。$ m $はサイズです。メインメモリのうち、$ k $ way QuickSortを使用する場合。 MergESORTはクイックソートと同じキャッシュ効率も備えており、そのkウェイバージョンは、メモリが深刻な制約である場合、（より低い定数因子を介して）より良いパフォーマンスを持っていることに注意してください。これにより、次のポイントが生まれます。他の要因でQuickSortとMergESORTを比較する必要があります。

クイックソートは通常、Mergesortよりも高速です

この比較は、完全に一定の要因に関するものです（典型的なケースを考慮した場合）。特に、選択は、Mergesortの入力全体のコピー（またはこのコピーを避けるために必要なアルゴリズムの複雑さ）と比較して、QuickSortのピボットの選択的な選択です。前者はより効率的であることがわかりました。この背後には理論はありません。たまたま速くなります。

QuickSortはより多くの再帰的な呼び出しを行いますが、スタックスペースを割り当てることは安価です（実際、スタックを吹き飛ばさない限り、ほぼ無料です）。ヒープに巨大なブロックを割り当てる（またはハードドライブ、$ n $が本当大規模）はかなり高価ですが、どちらも$ o（ log n）$のオーバーヘッドです。

最後に、クイックソートは、たまたま正しい順序である入力にわずかに敏感であることに注意してください。その場合、いくつかのスワップをスキップできます。 Mergesortにはこのような最適化はありません。これにより、Mergesortに比べてクイックソートが少し速くなります。

ニーズに合ったソートを使用してください

結論として：ソートアルゴリズムは常に最適ではありません。ニーズに合った方を選択してください。ほとんどの場合、最も速いアルゴリズムが必要であり、まれなケースでは少し遅くなることを気にしないでください。安定した種類は必要ありません。クイックソートを使用してください。それ以外の場合は、ニーズに合ったアルゴリズムを使用してください。

私の大学のプログラミングチュートリアルの1つで、学生にクイックソート、Mergesort、挿入ソートとPythonの組み込みリストのパフォーマンスを比較するように依頼しました。ティムソート）。組み込みのリストが組み込まれているため、実験結果は、他のソートアルゴリズムよりもはるかに優れたパフォーマンスを発揮して以来、私を深く驚かせました。したがって、通常のクイックソートの実装が実際に最高であると結論付けるのは時期尚早です。しかし、クイックソートのより良い実装、またはそのハイブリッドバージョンの実装がはるかに優れていると確信しています。

これは素敵なブログ記事ですデビッド・R・マシバー Timsortを適応型Mergesortの形式として説明します。

QuickSortが他のソートアルゴリズムと比較して非常に速い理由の1つは、キャッシュに優しいからだと思います。 QSが配列のセグメントを処理すると、セグメントの開始と終了時に要素にアクセスし、セグメントの中心に向かって移動します。

したがって、開始すると、配列の最初の要素にアクセスし、メモリ（「場所」）がキャッシュにロードされます。そして、2番目の要素にアクセスしようとすると、それは（おそらく）すでにキャッシュ中であるため、非常に速いです。

Heapsortのような他のアルゴリズムはこのように機能しません。それらは配列に大きくジャンプするため、遅くなります。

他の人はすでに漸近的であると言っています平均クイックソートのランタイムは、他のソートアルゴリズム（特定の設定で）よりも（定数で）優れています。

どういう意味ですか？順列がランダムに選択されていると仮定します（均一な分布を仮定）。この場合、典型的なピボット選択方法はピボットを提供します 期待して リスト/配列をほぼ半分に分割します。それが私たちを$ cal {o}（n log n）$に引き下げます。しかし、さらに、 マージ 再帰によって得られた部分的な解は、一定の時間のみに時間がかかります（Mergesortの場合の線形時間とは対照的に）。もちろん、ピボットに従って2つのリストの入力を分離すると線形時間がありますが、実際のスワップはほとんど必要ありません。

クイックソートには多くのバリエーションがあることに注意してください（例：Sedgewickの論文を参照）。それらは、異なる入力分布（均一で、ほぼ並べ替えられ、ほぼ反比例した、多くの重複、...）で異なる動作をします。他のアルゴリズムはより良いかもしれません。

注目に値する別の事実は、QuickSortがそうであることです スロー オーバーヘッドが少ないSimperアルゴリズムと比較した短い入力。したがって、優れたライブラリは長さ1のリストまで再走りませんが、入力長が約10ドルよりも小さい場合は（たとえば）挿入ソートを使用します。

$ o（n lg n）$の時間の複雑さを持つ他の比較ベースのソートアルゴリズムと比較して、クイックソートは、インプレースソートアルゴリズムであるため、Merge-Sortのような他のアルゴリズムよりも優れていると考えられています。言い換えれば、配列のメンバーを保存するために（もっと多くの）メモリを必要としません。

PS：正確には、他のアルゴリズムよりも優れていることはタスクに依存します。一部のタスクでは、他のソートアルゴリズムを使用する方が良いかもしれません。

参照：

Quick-Sortには$ Theta（n^2）$の最悪の実行時間がありますが、Quicksortは平均で非常に効率的であるため、最高の並べ替えと見なされます。）$他のソートアルゴリズムと比較して定数が非常に小さい場合。これが、他のソートアルゴリズムでクイックソートを使用する主な理由です。

2番目の理由は、それが実行されることです in-place 並べ替えと仮想メモリ環境で非常にうまく機能します。

アップデート： ：（ヤノマとスヴィックのコメントの後）

これをよりよく説明するために、マージソートを使用して例を挙げましょう（マージソートはクイックソートの後に次に広く採用されたソートアルゴリズムであるため、私は思う）、余分な定数がどこから来るのかを教えてください（私の知る限り、なぜ私が思うのかを教えてくださいクイックソートの方が優れています）：

次の合成を検討してください。

12,30,21,8,6,9,1,7. The merge sort algorithm works as follows:

(a) 12,30,21,8    6,9,1,7  //divide stage
(b) 12,30   21,8   6,9   1,7   //divide stage
(c) 12   30   21   8   6   9   1   7   //Final divide stage
(d) 12,30   8,21   6,9   1,7   //Merge Stage
(e) 8,12,21,30   .....     // Analyze this stage

最後の段階がどのように起こっているかを完全に見ている場合、最初の12と比較されるのは、最初に順になります。これで12が再び21と12が次に行くなどと比較されます。最終的なマージ、つまり4つの他の要素を含む4つの要素を使用すると、クイックソートで発生しない定数として多くの追加の比較が発生します。これが、クイックソートが好まれる理由です。

実際のデータを使用した私の経験はそれです QuickSortは貧弱な選択です. 。 QuickSortはランダムデータでうまく機能しますが、実際のデータはランダムではないことが多くあります。

2008年に、QuickSortの使用まで吊り下げソフトウェアのバグを追跡しました。しばらくして、挿入ソート、クイックソート、ヒープソート、マージソートの単純な埋め込みを書き、テストしました。私のマージソートは、大規模なデータセットで作業しながら、他のすべてを上回りました。

それ以来、マージソートは私のソートアルゴリズムの選択です。エレガントです。実装するのは簡単です。安定した種類です。 QuickSortのように、それは二次的な動作に退化することはありません。挿入ソートに切り替えて、小さな配列をソートします。

多くの場合、特定の実装は、クイックソートにとって実際にクイックソートではないことを確認するためだけに、特定の実装が驚くほどうまく機能すると考えていました。実装がQuickSortと別のアルゴリズムの間を切り替えて、QuickSortをまったく使用しない場合があります。例として、GLIBCのQSORT（）関数は実際にマージソートを使用します。作業スペースを割り当てる場合にのみ失敗しますか？コードが「より遅いアルゴリズム」とコメントするコメント.

編集：Java、Python、Perlなどのプログラミング言語では、Merge Sort、またはより正確には、TimsortやMerge Sortなどの派生物を使用して、小さなセットには挿入ソートも使用します。（Javaはまた、プレーンクイックソートよりも速いデュアルピボットクイックソートを使用しています。）

1 - クイックソートは整備されています（一定の量以外の余分なメンバーは必要ありません。）

2 - クイックソートは、他の効率的なソートアルゴリズムよりも実装しやすいです。

3 - クイックソートには、他の効率的なソートアルゴリズムよりも、実行時間の一定の要因が小さくなります。

更新：マージソートの場合、マージする前にデータを保存するために追加の配列が必要な「マージ」を実行する必要があります。しかし、クイックソートでは、あなたはそうしません。そのため、クイックソートが登場します。また、マージソートの一定因子を増加させるマージのためにいくつかの追加の比較が行われます。

特定のソートアルゴリズムは実際に最速の条件ではどのような条件ですか？

1）ハードウェアで並行して実装された場合、可能な限り少ないゲートを必要としながら、適度に低いレイテンシを持つ必要がありますか？はい - >ビットニックソーターまたはバッチャーを使用して、オッド - ネクタイのmergESORT、レイテンシは$ theta（ log（n）^2）$であり、コンパレータとマルチプレクサの数は$ theta（n cdot log（n）^です2）$。

2）各要素にはいくつの異なる値がありますか？缶あらゆる可能な値がメモリまたはキャッシュに一意の場所を割り当てています>> count sortまたはradix sortを使用します。通常、$ theta（n cdot k）$（count sort）または$ theta（nの線形ランタイムがあります。 cdot m）$（bucket sort）ただし、$ k = 2^{＃number _of _possible _values} $および$ m = #maximum _length _of として、多数の異なる値の場合は遅くなります。 _keys $。

3）基礎となるデータ構造は、リンクされた要素で構成されていますか？はい - >常に配置されたマージソートで使用します。リンクされたデータ構造のために、固定サイズまたは適応型（別名自然）のボトムアップは、リンクされたデータ構造のために異なるアリットの種類のマージを簡単に実装できます。また、各ステップでデータ全体をコピーする必要はなく、再帰も必要としないため、他の一般的な比較ベースのソートよりも高速で、クイックソートよりも高速です。

4）ソートは安定している必要がありますか？はい - >並べ替えのソートを安定化するために、迅速な並べ替えが好まれる場合でも、基礎となるデータ構造と予想されるデータの構造と予想される種類に応じて、固定サイズまたは適応型のマージソートを使用します。アルゴリズムには、元のインデックスで構成される最悪の場合に$ theta（n）$追加メモリが必要です。これは、入力データで実行される各スワップと同期する必要があります。オーバーマージソートはおそらく妨害されます。

5）基礎となるデータのサイズは、小規模から中型にバインドできますか？たとえば、n <10,000 ... 100,000,000（基礎となるアーキテクチャとデータ構造に応じて）？はい - > Bitonic SortまたはBatcher Odd -ven Mergesortを使用します。 GOTO 1）

6）別の$ theta（n）$メモリを省できますか？はい - > a）入力データは、すでにソートされたシーケンシャルデータの大きな部分で構成されていますか？ - > Adaptive（別名自然）マージソートまたはTimソートはい - > b）入力データは、ほとんど正しい場所にある要素で構成されていますか？ - >バブルソートまたは挿入ソートを使用します。彼らの$ theta（n^2）$の時間の複雑さ（これはほぼ並べ替えられたデータの病理学的）を恐れている場合は、（ほぼ）漸近的に最適なギャップシーケンスでシェルに切り替えることを検討するかもしれません。 n cdot log（n）^2）$最悪の場合の実行時間がわかっているか、櫛のソートを試してください。シェルソートまたはコームソートが実際にかなり良いパフォーマンスを発揮するかどうかはわかりません。

いいえ - > 7）別の$ theta（ log（n））$メモリをspareしみませんか？はい - > a）途方もないデータ構造は、指示されたシーケンシャルアクセスを許可していますか？はい - >データの終わりまで一度に1つの読み取り/書き込みアクセスのみが1つのシーケンスに到達されますか（例えば、テープアクセスなど）？はい - > i）マージソートを使用しますが、このケースを配置する明白な方法はありません。そのため、追加の$ theta（n）$メモリが必要になる場合があります。しかし、それを行う時間とボールがある場合、$ theta（n）$の時間に2つの配列をマージする方法があります。 Donald E. Knuth「コンピュータープログラミングの芸術、第3巻：並べ替えと検索」、演習5.5.3。 L. Trabb-Pardoによるアルゴリズムがあると述べています。ただし、これは、Naive Mergesortバージョンまたは上記のケースのクイックソートよりも速くなるとは思いません。いいえ、一連のデータへの複数の同時アクセスを可能にします（例えば、テープドライブではありません） - > ii）QuickSortを使用します。実用的な目的で、ランダム化または近似の中央値のいずれかをお勧めします。病理学的$ theta（n^2）$ケースに注意している場合は、イントロソートの使用を検討してください。決定論的な動作について地獄に屈している場合は、中央メディアンアルゴリズムを使用してピボット要素を選択することを検討する場合は、$ theta（n）$の時間が必要であり、その素朴な実装には$ theta（n）$ spaceが必要です（並列化可能）、$ theta（ log（n））$ space（並列化できない）のみを必要とするように実装される場合があります。ただし、中央メディアンアルゴリズムの中央値は、最悪の場合は$ theta（n cdot log（n））$ run-timeを備えた決定論的なクイックソートを提供します。いいえ - >ねじ込まれています（申し訳ありませんが、各データ要素に一度アクセスするには少なくとも1つの方法が必要です）

いいえ - > 8）少量の一定のメモリをspareしみませんか？はい - >基礎となるデータ構造はランダムアクセスを可能にしますか？はい - > heapsortを使用すると、$ theta（n cdot log（n））$の漸近最適な実行時間がありますが、Dismal Cache Coherencyであり、うまく並列化されていません。いいえ - >あなたはねじ込まれていません - >あなたはねじ込まれています

QuickSortの実装ヒント：

1）ナイーブバイナリクイックソートには$ theta（n）$追加メモリが必要ですが、最後の再帰呼び出しをループに書き直すことにより、それを$ theta（ log（n））$に減らすことは比較的簡単です。 K> 2のk-ary QuickSortsについても同じことを行うには、$ theta（n^{ log_k（k-1）}）$ space（マスター定理による）が必要です。 K> 2のK-アリークイックソートが、現実世界のセットアップでのバイナリクイックソートよりも高速であるかどうかを知っている人を聞いてうれしいです。

2）クイックソートのボトムアップ、反復バリアントが存在しますが、AFAIK、それらはトップダウンの境界と同じ漸近空間と時間の境界を持っています。私の経験では、実用的な目的のために、それらは決して検討する価値がないということです。

Mergesortの実装ヒント：

1）Bottum-Up Mergesortは、再帰呼び出しを必要としないため、トップダウンMergesortよりも常に高速です。

2）非常に素朴なMergESORTは、ダブルバッファーを使用してスピードアップし、各ステップの後に時間配列からデータをコピーする代わりにバッファを切り替えることができます。

3）多くの現実世界のデータでは、適応型Mergesortは固定サイズのMergesortよりもはるかに高速です。

4）マージアルゴリズムは、入力データをほぼ同じサイズの部分に分割することで簡単に並列化できます。これにはデータへのk参照が必要であり、K（または小さな定数C> = 1の場合はC*K）のすべてのk（またはC*k）が最も近いメモリ階層（通常はL1データキャッシュ）に適合するようにKを選択することは良いことです。 k要素から最小の選択を選択するナイーブの方法（線形検索）は$ theta（k）$時間を要しますが、それらのk要素内で最小ヒープを構築し、最小の要素を選択するには、償却$ theta（ log（ log）のみが必要です。 k））$ time（もちろん、最小値を選択するのは$ theta（1）$ですが、1つの要素が削除され、各ステップで別の要素に置き換えられるため、少しメンテナンスを行う必要があります）。並列化されたマージには、kに関係なく、常に$ theta（n）$メモリが必要です。

私が書いたものから、クイックソートはしばしば最速のアルゴリズムではないことは明らかです。ただし、次の条件がすべて適用される場合を除きます。

1）「少数の」可能な値以上があります

2）基礎となるデータ構造はリンクされていません

3）安定した順序は必要ありません

4）データが十分に大きくなるほど、ビットソリックソーターまたはバッチャーのオッド - even mergesortのわずかな漸近実行時間がキックインするほど大きいです

5）データはほとんどソートされておらず、既にソートされたより大きな部品で構成されていません

6）複数の場所からデータシーケンスに同時にアクセスできます

7）{メモリの書き込みは特に高価です（これはMergesortの主な欠点だからです）。これは、クイックソートの可能性のある最適な分割を超えてアルゴリズムを遅くすることです。 }または{$ theta（ log（n））$追加メモリ、$ theta（n）$が多すぎる（外部ストレージなど）}のみを使用できます}

PS：誰かがテキストのフォーマットを手伝う必要があります。

ソーティング方法のほとんどは、データを短いステップで移動する必要があります（たとえば、マージのソートはローカルで変更を行い、この小さなデータをマージし、より大きなデータをマージします。..）。その結果、データが目的地から遠く離れている場合、多くのデータ移動が必要です。

Quicksortは、反対側の数字を交換しようとします。メモリの最初の部分にあり、アレイの2番目の部分にあり、小さい数字があります（$ a le b $、議論は他の意味でも同じです）ので、彼らは最終目的地の近くにすばやく割り当てられます。

ライセンス： CC-BY-SA と帰属

所属していません cs.stackexchange