Quicksort vs. Heapsort

Question

Sowohl Quicksort als auch Heapsort sortieren an Ort und Stelle. Was ist besser? Bei welchen Anwendungen und in welchen Fällen ist eine der beiden Methoden vorzuziehen?

Answer 1

Heapsort ist garantiert O(N log N), was viel besser ist als der schlechteste Fall bei Quicksort. Heapsort benötigt nicht mehr Speicher für ein weiteres Array, um geordnete Daten abzulegen, wie dies bei Mergesort der Fall ist. Warum also bleiben kommerzielle Anwendungen bei Quicksort? Was ist das Besondere an Quicksort im Vergleich zu anderen Implementierungen?

Ich habe die Algorithmen selbst getestet und festgestellt, dass Quicksort in der Tat etwas Besonderes ist. Er läuft schnell, viel schneller als Heap- und Merge-Algorithmen.

Das Geheimnis von Quicksort ist: Es werden fast keine unnötigen Elementtauschvorgänge durchgeführt. Vertauschen ist zeitaufwendig.

Mit Heapsort müssen Sie, selbst wenn alle Daten bereits geordnet sind, 100 % der Elemente austauschen, um das Array zu ordnen.

Bei Mergesort ist es noch schlimmer. Sie werden 100 % der Elemente in ein anderes Array schreiben und in das ursprüngliche Array zurückschreiben, auch wenn die Daten bereits geordnet sind.

Mit Quicksort tauschen Sie nicht aus, was bereits bestellt ist. Wenn Ihre Daten vollständig geordnet sind, tauschen Sie fast nichts aus! Obwohl man sich viel über den schlimmsten Fall aufregt, kann man ihn durch eine kleine Verbesserung bei der Wahl des Pivotpunktes vermeiden, indem man nicht das erste oder letzte Element des Arrays nimmt. Wenn Sie einen Pivot aus dem Zwischenelement zwischen dem ersten, dem letzten und dem mittleren Element wählen, reicht das aus, um den schlimmsten Fall zu vermeiden.

Was bei Quicksort besser ist, ist nicht der schlechteste, sondern der beste Fall! Im besten Fall führen Sie die gleiche Anzahl von Vergleichen durch, aber Sie tauschen fast nichts aus. Im mittleren Fall tauschen Sie einen Teil der Elemente aus, aber nicht alle Elemente, wie bei Heapsort und Mergesort. Das ist es, was Quicksort die beste Zeit verschafft. Weniger Tauschvorgänge, mehr Geschwindigkeit.

Die folgende Implementierung in C# auf meinem Computer, die im Freigabemodus läuft, schlägt Array.Sort um 3 Sekunden mit mittlerem Pivot und um 2 Sekunden mit verbessertem Pivot (ja, es gibt einen Overhead, um einen guten Pivot zu erhalten).

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);
}

Answer 2

Dieses Papier enthält einige Analysen.

Außerdem, aus Wikipedia:

Der direkteste Konkurrent von quicksort ist heapsort. Heapsort ist in der Regel etwas langsamer als quicksort, aber die Laufzeit im schlimmsten Fall Zeit ist immer (nlogn). Quicksort ist in der Regel schneller, aber es bleibt die Möglichkeit der Worst-Case-Leistung außer bei der Introsort-Variante, die auf Heapsort umschaltet, wenn ein ungünstiger Fall erkannt wird. Wenn im Voraus bekannt ist dass Heapsort notwendig sein wird notwendig sein wird, ist seine direkte Verwendung schneller als das Warten auf Introsort zu wechseln.

Answer 3

Für die meisten Situationen, mit schnell vs. ein wenig schneller ist irrelevant ... Sie einfach nie wollen, dass es gelegentlich bekommen waayyy langsam. Zwar kann man QuickSort so optimieren, dass es nicht zu langsam wird, doch verliert man dabei die Eleganz des grundlegenden QuickSort. Für die meisten Dinge bevorzuge ich daher HeapSort... man kann es in seiner vollen, einfachen Eleganz implementieren und bekommt nie eine langsame Sortierung.

In Situationen, in denen Sie in den meisten Fällen maximale Geschwindigkeit wünschen, kann QuickSort gegenüber HeapSort bevorzugt werden, aber keines von beiden kann die richtige Antwort sein. In geschwindigkeitskritischen Situationen lohnt es sich, die Details der Situation genau zu untersuchen. In einigen meiner geschwindigkeitskritischen Codes ist es zum Beispiel sehr häufig der Fall, dass die Daten bereits sortiert oder fast sortiert sind (es werden mehrere zusammenhängende Felder indiziert, die sich oft entweder zusammen auf- und abwärts bewegen ODER einander gegenüber auf- und abwärts bewegen, so dass, sobald man nach einem sortiert, die anderen entweder sortiert oder umgekehrt sortiert sind oder nahe dran sind... beides kann QuickSort zerstören). Für diesen Fall habe ich weder das eine noch das andere implementiert... stattdessen habe ich Dijkstras SmoothSort implementiert... eine HeapSort-Variante, die O(N) ist, wenn sie bereits sortiert oder fast sortiert ist... sie ist nicht so elegant, nicht so einfach zu verstehen, aber schnell... lesen http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD796a.PDF wenn Sie eine etwas anspruchsvollere Programmierung wünschen.

Answer 4

Quicksort-Heapsort-Hybride sind ebenfalls sehr interessant, da die meisten von ihnen im schlimmsten Fall nur n*log n Vergleiche benötigen (sie sind optimal in Bezug auf den ersten Term der Asymptotik, so dass sie die Worst-Case-Szenarien von Quicksort vermeiden), O(log n) zusätzlichen Platz und sie bewahren mindestens "die Hälfte" des guten Verhaltens von Quicksort in Bezug auf bereits geordnete Datenmengen. Ein äußerst interessanter Algorithmus wird von Dikert und Weiss vorgestellt in http://arxiv.org/pdf/1209.4214v1.pdf :

• Wählen Sie einen Pivot p als Median einer Zufallsstichprobe von sqrt(n) Elementen (dies kann in höchstens 24 sqrt(n)-Vergleichen mit dem Algorithmus von Tarjan&co oder in 5 sqrt(n)-Vergleichen mit dem viel komplizierteren Spider-Factory-Algorithmus von Schonhage geschehen);
• Teilen Sie Ihr Array in zwei Teile auf, wie im ersten Schritt von Quicksort;
• Heapify den kleinsten Teil und verwenden O(log n) zusätzliche Bits, um einen Heap zu kodieren, in dem jedes linke Kind einen größeren Wert als sein Geschwister hat;
• Rekursiv die Wurzel des Haufens extrahieren, die Lücke, die die Wurzel hinterlässt, durchsieben, bis sie ein Blatt des Haufens erreicht, dann die Lücke mit einem geeigneten Element aus dem anderen Teil des Arrays füllen;
• Rekursion über den verbleibenden nicht geordneten Teil des Arrays (wenn p als exakter Median gewählt wird, gibt es überhaupt keine Rekursion).

Answer 5

Nun, wenn Sie auf Architekturebene gehen ... wir verwenden Warteschlange Datenstruktur in Cache memory.so, was auch immer in der Warteschlange verfügbar ist, wird sortiert.as in schnelle Sortierung haben wir kein Problem teilen das Array in jede lenght ... aber in Heap sort (durch die Verwendung von Array) kann es so passieren, dass der Elternteil möglicherweise nicht in der Sub-Array im Cache verfügbar und dann hat es in Cache-Speicher zu bringen ... was zeitaufwendig ist. Das ist quicksort ist am besten!!