108

Both quicksort and heapsort do in-place sorting. Which is better? What are the applications and cases in which either is preferred?

4

12 に答える 12

155

Heapsort は O(N log N) が保証されており、Quicksort の最悪のケースよりもはるかに優れています。ヒープソートは、マージソートで必要とされるように、順序付けられたデータを配置するために別の配列に追加のメモリを必要としません。では、商用アプリケーションが Quicksort に固執するのはなぜでしょうか? 他の実装よりも特別な Quicksort は何ですか?

私は自分でアルゴリズムをテストしましたが、Quicksort には確かに特別な機能があることがわかりました。ヒープおよびマージ アルゴリズムよりもはるかに高速に実行されます。

クイックソートの秘密は、不必要な要素の交換をほとんど行わないことです。交換は手間です。

ヒープソートを使用すると、すべてのデータが既に順序付けられている場合でも、要素を 100% 交換して配列を順序付けることになります。

Mergesort を使用すると、さらに悪化します。データが既に順序付けられている場合でも、要素の 100% を別の配列に書き込み、元の配列に書き戻します。

クイックソートを使用すると、すでに注文されたものを交換しません。データが完全に順序付けられている場合、ほとんど何も交換しません! 最悪のケースについて多くの騒ぎがありますが、配列の最初または最後の要素を取得する以外のピボットの選択を少し改善することで、それを回避できます。最初、最後、および中間要素の間の中間要素からピボットを取得する場合、最悪のケースを回避するのに十分です。

クイックソートで優れているのは、最悪の場合ではなく、最良の場合です! 最良の場合、同じ数の比較を行いますが、ほとんど何も交換しません。通常、Heapsort や Mergesort のように、要素の一部を交換しますが、すべての要素を交換するわけではありません。それが、Quicksort に最適な時間を提供する理由です。スワップが減り、速度が向上します。

リリース モードで実行されている私のコンピューターの C# での以下の実装は、中間ピボットで 3 秒、改善されたピボットで 2 秒、Array.Sort を上回ります (はい、適切なピボットを取得するためのオーバーヘッドがあります)。

static void Main(string[] args)
{
    int[] arrToSort = new int[100000000];
    var r = new Random();
    for (int i = 0; i < arrToSort.Length; i++) arrToSort[i] = r.Next(1, arrToSort.Length);

    Console.WriteLine("Press q to quick sort, s to Array.Sort");
    while (true)
    {
        var k = Console.ReadKey(true);
        if (k.KeyChar == 'q')
        {
            // quick sort
            Console.WriteLine("Beg quick sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));
            QuickSort(arrToSort, 0, arrToSort.Length - 1);
            Console.WriteLine("End quick sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));
            for (int i = 0; i < arrToSort.Length; i++) arrToSort[i] = r.Next(1, arrToSort.Length);
        }
        else if (k.KeyChar == 's')
        {
            Console.WriteLine("Beg Array.Sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));
            Array.Sort(arrToSort);
            Console.WriteLine("End Array.Sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));
            for (int i = 0; i < arrToSort.Length; i++) arrToSort[i] = r.Next(1, arrToSort.Length);
        }
    }
}

static public void QuickSort(int[] arr, int left, int right)
{
    int begin = left
        , end = right
        , pivot
        // get middle element pivot
        //= arr[(left + right) / 2]
        ;

    //improved pivot
    int middle = (left + right) / 2;
    int
        LM = arr[left].CompareTo(arr[middle])
        , MR = arr[middle].CompareTo(arr[right])
        , LR = arr[left].CompareTo(arr[right])
        ;
    if (-1 * LM == LR)
        pivot = arr[left];
    else
        if (MR == -1 * LR)
            pivot = arr[right];
        else
            pivot = arr[middle];
    do
    {
        while (arr[left] < pivot) left++;
        while (arr[right] > pivot) right--;

        if(left <= right)
        {
            int temp = arr[right];
            arr[right] = arr[left];
            arr[left] = temp;

            left++;
            right--;
        }
    } while (left <= right);

    if (left < end) QuickSort(arr, left, end);
    if (begin < right) QuickSort(arr, begin, right);
}
于 2015-02-15T03:55:48.080 に答える
68

この論文にはいくつかの分析があります。

また、ウィキペディアから：

クイックソートの最も直接的な競合相手はヒープソートです。通常、ヒープソートはクイックソートよりも多少遅くなりますが、最悪の場合の実行時間は常に Θ(nlogn) です。悪いケースが検出されたときにヒープソートに切り替わるイントロソートのバリアントを除いて、最悪のケースのパフォーマンスの可能性は残っていますが、通常はクイックソートの方が高速です。ヒープソートが必要になることが事前にわかっている場合は、イントロソートが切り替わるのを待つよりも、ヒープソートを直接使用する方が高速です。

于 2010-03-18T05:48:13.747 に答える
16

ほとんどの状況では、速いか少し速いかは関係ありません...時々遅くなることは決してありません。QuickSort を微調整して速度の遅い状況を回避することはできますが、基本的な QuickSort の優雅さは失われます。したがって、ほとんどの場合、私は実際には HeapSort を好みます...完全にシンプルなエレガンスで実装でき、ソートが遅くなることはありません。

ほとんどの場合、最大速度が必要な状況では、HeapSort よりも QuickSort が優先される場合がありますが、どちらも正しい答えではない可能性があります。速度が重要な状況では、状況の詳細を綿密に調べる価値があります。たとえば、スピード クリティカルなコードの一部では、データが既に並べ替えられているか、ほぼ並べ替えられていることが非常に一般的です (複数の関連するフィールドにインデックスを付けており、これらのフィールドはしばしば一緒に上下に移動するか、上下に反対方向に移動します。そのため、1 つで並べ替えると、他のものは並べ替えられているか、逆に並べ替えられているか、近くに配置されています...どちらも QuickSort を強制終了する可能性があります)。その場合、どちらも実装しませんでした...代わりに、Dijkstra の SmoothSort を実装しました...既に並べ替えられているか、並べ替えられているときに O(N) である HeapSort バリアント...それほどエレガントではなく、理解しやすいものでもありません。しかし速い... 読むhttp://www.cs.utexas.edu/users/EWD/ewd07xx/EWD796a.PDFを参照してください。もう少し難しいコードが必要な場合。

于 2011-10-03T05:10:30.127 に答える
6

クイックソートとヒープソートのインプレース ハイブリッドも非常に興味深いものです。それらのほとんどは、最悪の場合でも n*log n の比較しか必要としないためです (漸近法の最初の項に関して最適であるため、最悪のシナリオを回避します)。 O(log n) 余分なスペースがあり、既に順序付けられたデータ セットに関して、Quicksort の適切な動作の少なくとも「半分」が保持されます。非常に興味深いアルゴリズムが Dikert と Weiss によってhttp://arxiv.org/pdf/1209.4214v1.pdfで紹介されています。

  • sqrt(n) 要素のランダム サンプルの中央値としてピボット p を選択します (これは、Tarjan&co のアルゴリズムによる最大 24 の sqrt(n) 比較、またははるかに複雑なスパイダーによる 5 sqrt(n) の比較で実行できます)。 -Schonhage のファクトリ アルゴリズム);
  • クイックソートの最初のステップと同様に、配列を 2 つの部分に分割します。
  • 最小部分をヒープ化し、O(log n) 余分なビットを使用して、左側のすべての子がその兄弟より大きい値を持つヒープをエンコードします。
  • ヒープのルートを再帰的に抽出し、ヒープのリーフに到達するまで、ルートによって残されたラクーンをふるいにかけます。次に、配列の他の部分から取得した適切な要素でラクーンを埋めます。
  • 配列の残りの順序付けされていない部分を繰り返します (p が正確な中央値として選択されている場合、再帰はまったくありません)。
于 2013-01-21T15:23:51.230 に答える
2

アーキテクチャレベルに行くと...キャッシュメモリでキューデータ構造を使用するため、キューで利用可能なものはすべてソートされます.クイックソートと同様に、配列を任意の長さに分割しても問題はありません...しかしヒープで（配列を使用して）ソートすると、キャッシュで使用可能なサブ配列に親が存在しない可能性があり、それをキャッシュメモリに入れる必要があります...これには時間がかかります。それはクイックソートが最適です!!

于 2016-05-20T21:03:21.560 に答える
2

ヒープソートにはO(n*log(n))という最悪の実行ケースがあるという利点があるため、クイックソートのパフォーマンスが低下する可能性がある場合 (ほとんどの場合、一般的にソートされたデータ セット) は、ヒープソートがはるかに優先されます。

于 2010-03-18T05:48:54.850 に答える
2

私にとって、ヒープソートとクイックソートには非常に根本的な違いがあります。後者は再帰を使用します。再帰アルゴリズムでは、再帰の回数に応じてヒープが大きくなります。nが小さい場合は問題ありませんが、現在、 n = 10^9の 2 つの行列を並べ替えています!!. このプログラムは約 10 GB の RAM を消費し、余分なメモリがあると、コンピュータは仮想ディスク メモリへのスワップを開始します。私のディスクは RAM ディスクですが、それでもスワップすると速度が大幅に変わります。そのため、C++ でコード化された statpack には、サイズが事前にプログラマーに知られていない調整可能な次元マトリックスと、非パラメトリックな統計的並べ替えが含まれており、非常に大きなデータ マトリックスを使用する際の遅延を回避するために、ヒープソートを好みます。

于 2016-04-16T00:08:06.330 に答える
2

コンプ。quick sort両方ともインプレースソートのタイプであるため、最悪の場合の実行時間には違いmerge sortがあります。最悪の場合の実行時間はクイックソートの場合とヒープソートの場合O(n^2)は変わらO(n*log(n))ず、平均的なデータ量の場合はクイックソートの方が便利です。ランダム化されたアルゴリズムであるため、正しい ans を取得する確率。選択したピボット要素の位置によって異なります。

だから

Good call: L と G のサイズがそれぞれ 3s/4 未満

不正な呼び出し: L と G のいずれかのサイズが 3s/4 より大きい

少量の場合は挿入ソートを使用でき、非常に大量のデータの場合はヒープソートを使用できます。

于 2012-09-26T17:18:17.570 に答える
1

ヒープ ソートは、非常に大きな入力を処理する場合に安全な方法です。漸近分析により、最悪の場合のヒープソートの成長の順序は であり、最悪の場合Big-O(n logn)のクイックソートよりも優れていBig-O(n^2)ます。ただし、ヒープソートは、ほとんどのマシンで実際には、適切に実装されたクイック ソートよりも多少遅くなります。ヒープソートも安定したソート アルゴリズムではありません。

実際にヒープソートがクイックソートよりも遅い理由は、データ要素が比較的近いストレージの場所にあるクイックソートの参照の局所性 (" https://en.wikipedia.org/wiki/Locality_of_reference ") が優れているためです。強力な参照局所性を示すシステムは、パフォーマンス最適化の優れた候補です。ただし、ヒープソートはより大きな飛躍を扱います。これにより、クイックソートは小さな入力に対してより有利になります。

于 2015-11-26T17:02:38.450 に答える
1

Heapsortはヒープを構築し、最大項目を繰り返し抽出します。その最悪のケースは O(n log n) です。

しかし、O(n2) であるクイック ソートの最悪のケースを見ると、クイック ソートは大きなデータにはあまり適していないことがわかります。

これにより、並べ替えが興味深いものになります。今日、非常に多くの並べ替えアルゴリズムが存在する理由は、それらすべてが最適な場所で「最適」であるためだと思います。たとえば、データがソートされている場合、バブル ソートはクイック ソートよりも優れています。または、ソートするアイテムについて何か知っていれば、おそらくもっとうまくやれるでしょう。

これはあなたの質問に直接答えないかもしれません.2セントを追加すると思いました.

于 2010-03-18T07:43:29.993 に答える
1

簡単に言うと >> HeapSort は、「O(n log n)」の QuickSort の ~平均~ 実行時間とは対照的に、「O(n log n)」の ~最悪の場合の~ 実行時間を保証しています。通常は QuickSort の方が高速であるため、実際には QuickSort が使用されますが、コンピューターのメモリに収まらない巨大なファイルを並べ替える必要がある場合は、HeapSort が外部並べ替えに使用されます。

于 2020-09-19T11:07:54.650 に答える
-1

元の質問に答えて、ここで他のコメントのいくつかに対処するには:

セレクション、クイック、マージ、およびヒープ ソートの実装を比較して、それらが互いにどのように積み重なっていくかを確認しました。答えは、それらすべてに欠点があるということです。

TL;DR: クイックは最良の汎用ソートです (適度に高速で、安定しており、ほとんどがインプレースです) 個人的には、安定したソートが必要でない限り、ヒープ ソートを好みます。

選択 - N^2 - 実際には 20 要素未満の場合にのみ有効であり、その後は優れています。データがすでにソートされているか、ほとんどソートされていない限り。N^2 は非常に遅くなり、非常に速くなります。

私の経験では、クイックは実際には常にそれほど高速ではありません。ただし、クイック ソートを一般的なソートとして使用する利点は、かなり高速で安定していることです。これもインプレース アルゴリズムですが、通常は再帰的に実装されるため、追加のスタック スペースが必要になります。また、O(n log n) と O(n^2) の間のどこかに収まります。特に値が狭い範囲内にある場合、いくつかの種類のタイミングがこれを確認しているようです。10,000,000 項目の選択ソートよりも高速ですが、マージやヒープよりは遅くなります。

マージソートはデータに依存しないため、O(n log n) が保証されます。あなたが与えた値に関係なく、それはそれがすることをするだけです。また、安定していますが、実装に注意しないと、非常に大きなソートによってスタックが吹き飛ばされる可能性があります。いくつかの複雑なインプレース マージ ソートの実装がありますが、通常、値をマージするには各レベルに別の配列が必要です。これらのアレイがスタック上に存在する場合、問題が発生する可能性があります。

ヒープの並べ替えは最大 O(n log n) ですが、多くの場合、log n の深いヒープで値をどれだけ上に移動する必要があるかによっては、より高速です。ヒープは元の配列のインプレースで簡単に実装できるため、追加のメモリは必要なく、反復的であるため、再帰中のスタック オーバーフローの心配もありません。ヒープ ソートの大きな欠点は、安定したソートではないことです。つまり、必要な場合は問題ありません。

于 2016-04-09T21:32:37.643 に答える