a への挿入の最悪の場合の実行時間は でred-black treeあり、ツリーでO(lg n)a を実行する場合in-order walk、基本的に各ノードにアクセスするため、ソートされたコレクションを出力するための最悪の場合の合計実行時間は O(n lg n) になります。
私は興味があります.なぜred-black treesソートに好まれないのですかquick sort（その平均ケースの実行時間はO(n lg n).
そのred-black trees場でソートしないためかもしれませんが、よくわからないので、誰かが助けてくれるかもしれません。
どのソートアルゴリズムのパフォーマンスが優れているかは、データと状況によって異なります。
あなたが一般的/実用的な言葉で話しているなら、
クイックソート（ピボットをランダムに選択する/固定されたものを1つ選択するだけで、最悪の場合はオメガ（n ^ 2））は、赤黒木よりも優れている可能性があります（必ずしも重要度の高い順にはなりません）。
クイックソートはインプレースです。はメモリフットプリントを低く保ちます。このクイックソートルーチンは、大量のデータを処理するプログラムの一部だったとしましょう。大量のメモリを使い続けると、OSがプロセスメモリの交換を開始し、パフォーマンスを破壊する可能性があります。
クイックソートメモリアクセスはローカライズされています。これは、キャッシング/スワッピングでうまく機能します。
クイックソートは簡単に並列化できます（おそらく最近はもっと関連性があります）。
代わりに配列を使用して（バランスをとらずにバイナリツリーを使用して）バイナリツリーの並べ替えを最適化しようとすると、Quicksortのようなことをすることになります。
赤黒木にはメモリオーバーヘッドがあります。ノードを複数回割り当てる必要があります。ツリーでのメモリ要件は、アレイを使用する場合の2倍/3倍です。
並べ替えた後、1045番目（たとえば）の要素が必要だとすると、ツリー内の順序統計を維持する必要があり（このため、余分なメモリコストがかかります）、O（logn）アクセス時間があります！
赤黒木には、次の要素にアクセスするためだけのオーバーヘッドがあります（ポインタールックアップ）
赤黒木はキャッシュでうまく機能せず、ポインターアクセスはより多くのスワッピングを引き起こす可能性があります。
赤黒木の回転は、O（nlogn）の定数係数を増加させます。
おそらく最も重要な理由（ただし、libなどが利用可能な場合は無効です）、Quicksortは理解と実装が非常に簡単です。学校の子供でも理解できます！
両方の実装を測定して、何が起こるかを確認してください。
また、ボブ・セッジウィックはクイックソートに関する論文を発表しました！読む価値があるかもしれません。
最悪の場合の並べ替えアルゴリズムはたくさんありO(n log n)ます。たとえば、マージ並べ替えです。クイックソートが好まれる理由は、アルゴリズム的には他のアルゴリズムほど良くないかもしれませんが、実際には高速だからです。
多くの場合、組み込みの並べ替えでは、n の値に応じてさまざまな方法を組み合わせて使用します。
セアカゴケは選別が悪くない場合が多いです。私のテストでは、自然なマージソートと比較して、赤黒木が次の場所で優れていることが示されました。
Dup にはツリーの方が適しています: Dup を排除する必要があるすべてのテストでは、ツリー アルゴリズムの方が優れています。ツリーは最初から非常に小さく保つことができるため、これは驚くべきことではありません。これにより、インライン配列ソート用に設計されたアルゴリズムは、より大きなセグメントを長時間通過する可能性があります。
Trees are better for Random: ランダム ツリー アルゴリズムを使用したすべてのテストが優れています。ツリーでは要素間の距離が短く、シフトが必要ないため、これも驚くべきことではありません。したがって、ツリーに繰り返し挿入することは、配列をソートするよりも労力が少なくて済みます。
そのため、ナチュラル マージ ソートは、昇順および降順の特殊なケースでのみ優れているという印象を受けます。クイックソートとは言えません。
ここでテストケースの要点を説明します。
PS: ソートにツリーを使用することは簡単ではないことに注意してください。挿入ルーチンを提供するだけでなく、ツリーを線形化して配列に戻すルーチンも提供する必要があります。現在、スタックを必要としない get_last と先行ルーチンを使用しています。しかし、これらのルーチンにはループが含まれているため、O(1) ではありません。
一般に、O(nlgn) アルゴリズムの表現は、A*nlgn + B に拡張できます。ここで、A と B は定数です。クイックソートの係数が他のアルゴリズムの係数よりも小さいことを示す多くのアルゴリズム証明があります。これは最良のケースです (クイック ソートは、ソートされたデータに対してひどく実行されます)。
Big-O の時間計算量の測定では、通常、スカラー ファクターは考慮されません。たとえば、O(2n) と O(4n) は、通常、O(n) に単純に縮小されます。時間計算量の分析は、厳密なプログラミング レベルではなく、アルゴリズム レベルでの操作ステップに基づいています。つまり、ソース コードやネイティブ マシン インストラクションは考慮されません。
クイックソートは一般に、ツリーベースのソートよりも高速です。これは、(1) メソッドのアルゴリズムの平均時間の複雑さが同じであり、(2) 単純な配列を使用する場合、赤黒ツリーを使用する場合よりもルックアップおよびスワッピング操作に必要なプログラム コマンドとデータ アクセスが少ないためです。ツリーが基礎となる配列ベースの実装を使用している場合でも。赤黒ツリーの制約を維持するには、クイックソートの単純な配列パーティション交換手順よりも、追加の操作手順、データ フィールド値の格納/アクセス (ノードの色) などが必要です。
最終的な結果として、赤黒木はクイックソートよりも高いスカラー係数を持ち、標準の O(n log n) 平均時間複雑度分析結果ではわかりにくくなっています。
マシン アーキテクチャに関連するその他の実用的な考慮事項については、ウィキペディアのクイックソートの記事で簡単に説明しています。
こんにちは、私の意見では、すべての並べ替えルーチンの違いを説明する最良の方法は. （私の答えは、クイックソートが実際には別のソートアルゴリズムよりも高速であることに混乱している人向けです）。
「非常に遅いコンピューターで実行していると思います」。
「時間の重要性を人々に理解してもらうためだけに時間を使っています」.
すべてのソート操作から、クイックソートでは比較が非常に少なくなり、要素の交換が非常に少なくなりました。
この主な理由により、クイックソートの方が高速です。