48

ヒープソートの複雑さは最悪の場合ですがO(nlogn)、クイックソートにはありO(n^2)ます。しかし、経験的な証拠は、クイックソートが優れていることを示しています。何故ですか？

4

6 に答える 6

63

主な要因の1つは、クイックソートの参照の局所性が優れていることです。次にアクセスするものは、通常、メモリ内で今見たものに近いものです。対照的に、ヒープソートはかなり多くジャンプします。近くにあるものは一緒にキャッシュされる可能性が高いため、クイックソートの方が高速になる傾向があります。

ただし、クイックソートの最悪の場合のパフォーマンスは、ヒープソートのパフォーマンスよりも大幅に劣ります。一部の重要なアプリケーションでは速度パフォーマンスの保証が必要になるため、このような場合はヒープソートが適切な方法です。

于 2009-12-05T19:41:39.427 に答える
22

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

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

クイックソートの秘密は次のとおりです。不要な要素の交換はほとんど行われません。スワップには時間がかかります。

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

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

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

クイックソートで優れているのは最悪の場合ではなく、最良の場合です。最良の場合、同じ数の比較を行いますが、ほとんど何も交換しません。通常、ヒープソートやマージソートのように、要素の一部を交換しますが、すべての要素を交換するわけではありません。それがクイックソートに最高の時間を与えるものです。スワップが少なく、速度が速い。

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

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-15T04:05:33.780 に答える
8

ここにいくつかの説明があります：

http://www.cs.auckland.ac.nz/software/AlgAnim/qsort3.html

http://users.aims.ac.za/~mackay/sorting/sorting.html

基本的に、クイックソートの最悪のケースはO（n ^ 2）ですが、平均してパフォーマンスが向上します。:-)

于 2009-12-05T19:40:46.183 に答える
1

big-O表記は、n個のアイテムを並べ替えるのに必要な時間が、関数によって制限されることを意味しますc*n*log(n)。ここで、cは不特定の定数係数です。cとの定数が同じである必要がある理由はありませquicksortんheapsort。ですから、本当の問題は、なぜそれらが同じくらい速いと期待するのかということです。

Quicksort常にheapsort実際よりもいくらか高速でしたが、前述のように、メモリアクセスの局所性が実行速度にとって非常に重要になっているため、最近ではその差が大きくなっています。

于 2010-07-31T13:29:39.660 に答える
0

平均的な場合の複雑さ、およびクイックソートで最悪の場合の複雑さのリスクを最小限に抑えるための簡単な手順を実行できるという事実（たとえば、単一の選択された位置ではなく、3つの要素の中央値としてピボットを選択します）。

于 2009-12-05T19:40:50.513 に答える
0

すでに述べたように、クイックソートはヒープソートに比べて参照の局所性がはるかに優れていますが、最悪の場合はO（n ^ 2）の複雑さがあります。

std :: sortは、イントロソートソートを使用して実装されます。ほとんどの場合クイックソートを実行しますが、ピボットの選択が不適切なためにランタイムが不良であることが検出された場合は、ヒープソートに切り替わります。その場合、ほぼ毎回選択されるクイックソートの速度とともに、保証されたO（nlog（n））の複雑さが得られます。

于 2021-01-06T16:10:25.677 に答える