Quicksort gegen Heapsort

Sowohl Quicksort als auch Heapsort sortieren vor Ort. Welches ist besser? In welchen Anwendungen und Fällen wird beides bevorzugt?

Dieses Papier enthält einige Analysen.

Auch aus Wikipedia:

Der direkteste Konkurrent von Quicksort ist Heapsort. Heapsort ist normalerweise etwas langsamer als Quicksort, aber die Laufzeit im ungünstigsten Fall ist immer Θ (nlogn). Quicksort ist normalerweise schneller, obwohl die Wahrscheinlichkeit einer Worst-Case-Leistung bestehen bleibt, außer bei der Introsort-Variante, die auf Heapsort umschaltet, wenn ein schlechter Fall erkannt wird. Wenn im Voraus bekannt ist, dass Heapsort erforderlich sein wird, ist die direkte Verwendung schneller als das Warten auf den Wechsel von Introsort.

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

Ich habe die Algorithmen selbst getestet und festgestellt, dass Quicksort tatsächlich etwas Besonderes hat. Es läuft schnell, viel schneller als Heap- und Merge-Algorithmen.

Das Geheimnis von Quicksort ist: Es werden fast keine unnötigen Elementwechsel durchgeführt. Der Austausch ist zeitaufwändig.

Mit Heapsort werden Sie 100% der Elemente austauschen, um das Array zu ordnen, auch wenn alle Ihre Daten bereits bestellt sind.

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

Mit Quicksort tauschen Sie nicht das, was bereits bestellt wurde. Wenn Ihre Daten vollständig bestellt sind, tauschen Sie fast nichts aus! Obwohl der Worst-Case viel Aufhebens macht, kann eine kleine Verbesserung der Auswahl des Pivots, außer dem Erhalten des ersten oder letzten Elements des Arrays, dies vermeiden. Wenn Sie vom Zwischenelement zwischen dem ersten, dem letzten und dem mittleren Element einen Drehpunkt erhalten, reicht es aus, den schlimmsten Fall zu vermeiden.

Was in Quicksort überlegen ist, ist nicht der schlechteste, sondern der beste Fall! Im besten Fall führen Sie die gleiche Anzahl von Vergleichen durch, ok, aber Sie tauschen fast nichts aus. Im Durchschnitt tauschen Sie einen Teil der Elemente aus, jedoch nicht alle Elemente, wie in Heapsort und Mergesort. Das ist es, was Quicksort die beste Zeit gibt. Weniger Tausch, mehr Geschwindigkeit.

Die Implementierung unten in C # auf meinem Computer, die im Release-Modus ausgeführt wird, übertrifft 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);
}

In den meisten Situationen ist es irrelevant, schnell oder etwas schneller zu sein. Man möchte einfach nie, dass es gelegentlich langsam wird. Obwohl Sie QuickSort optimieren können, um langsame Situationen zu vermeiden, verlieren Sie die Eleganz des einfachen QuickSort. Für die meisten Dinge bevorzuge ich HeapSort ... Sie können es in seiner einfachen Eleganz implementieren und erhalten nie eine langsame Sortierung.

In Situationen, in denen Sie in den meisten Fällen maximale Geschwindigkeit wünschen, wird QuickSort möglicherweise HeapSort vorgezogen, aber beides ist möglicherweise nicht die richtige Antwort. In geschwindigkeitskritischen Situationen lohnt es sich, die Details der Situation genau zu untersuchen. In einigen meiner geschwindigkeitskritischen Codes ist es beispielsweise sehr häufig, dass die Daten bereits sortiert oder nahezu sortiert sind (es werden mehrere verwandte Felder indiziert, die sich häufig entweder zusammen auf und ab bewegen oder sich gegenüber auf und ab bewegen). Sobald Sie also nach einem sortieren, werden die anderen entweder sortiert oder umgekehrt sortiert oder geschlossen ... beides kann QuickSort töten. Für diesen Fall habe ich weder implementiert noch ... stattdessen habe ich Dijkstras SmoothSort implementiert ... eine HeapSort-Variante, die O (N) ist, wenn sie bereits sortiert oder nahezu sortiert ist ... sie ist nicht so elegant, nicht zu leicht zu verstehen, aber schnell ... lesenhttp://www.cs.utexas.edu/users/EWD/ewd07xx/EWD796a.PDF, wenn Sie etwas schwierigeres Code möchten.

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

• 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 mit 5 sqrt (n) -Vergleichen durch die viel kompliziertere Spinne erfolgen -Fabrikalgorithmus von Schönhage);
• Partitionieren Sie Ihr Array wie im ersten Schritt von Quicksort in zwei Teile.
• Heapifizieren Sie den kleinsten Teil und verwenden Sie O (log n) zusätzliche Bits, um einen Heap zu codieren, in dem jedes linke Kind einen Wert hat, der größer als sein Geschwister ist.
• Extrahieren Sie rekursiv die Wurzel des Haufens, sieben Sie die von der Wurzel hinterlassene Lücke ab, bis sie ein Blatt des Haufens erreicht, und füllen Sie die Lücke dann mit einem geeigneten Element aus dem anderen Teil des Arrays.
• Wiederholen Sie den Vorgang über den verbleibenden nicht geordneten Teil des Arrays (wenn p als exakter Median ausgewählt wird, gibt es überhaupt keine Rekursion).

Comp. zwischen quick sortund merge sortda beide Arten der In-Place-Sortierung sind, gibt es einen Unterschied zwischen der Laufzeit des Frostfalls und der Laufzeit des Frostfalls für die schnelle Sortierung O(n^2)und für die Heap-SortierungO(n*log(n)) und für eine durchschnittliche Datenmenge ist eine schnelle Sortierung nützlicher. Da es sich um einen randomisierten Algorithmus handelt, ist die Wahrscheinlichkeit, richtig zu werden, ans. in kürzerer Zeit hängt von der Position des von Ihnen gewählten Schwenkelements ab.

Also a

Guter Anruf: Die Größen von L und G sind jeweils kleiner als 3s / 4

Schlechter Anruf: Einer von L und G hat eine Größe von mehr als 3s / 4

Für kleine Mengen können wir die Einfügesortierung und für sehr große Datenmengen die Heap-Sortierung wählen.

Heapsort hat den Vorteil, dass O (n * log (n)) den schlechtesten Fall aufweist. In Fällen, in denen Quicksort wahrscheinlich eine schlechte Leistung erbringt (meistens sortierte Datensätze im Allgemeinen), wird Heapsort sehr bevorzugt.

Nun, wenn Sie auf Architekturebene gehen ... verwenden wir die Warteschlangendatenstruktur im Cache-Speicher. Was auch immer in der Warteschlange verfügbar ist, wird sortiert. Wie bei der schnellen Sortierung haben wir kein Problem damit, das Array in eine beliebige Länge zu unterteilen ... aber in Heap Beim Sortieren (mithilfe eines Arrays) kann es vorkommen, dass das übergeordnete Element nicht in dem im Cache verfügbaren Sub-Array vorhanden ist und es dann in den Cache-Speicher bringen muss ... was zeitaufwändig ist. Das ist Quicksort ist am besten !! 😀

Heapsort erstellt einen Heap und extrahiert dann wiederholt das maximale Element. Der schlimmste Fall ist O (n log n).

Wenn Sie jedoch den schlimmsten Fall einer schnellen Sortierung sehen würden , nämlich O (n2), würden Sie feststellen, dass eine schnelle Sortierung für große Datenmengen keine so gute Wahl wäre.

Das macht das Sortieren also zu einer interessanten Sache. Ich glaube, der Grund, warum heute so viele Sortieralgorithmen leben, ist, dass sie alle an ihren besten Stellen "am besten" sind. Beispielsweise kann die Blasensortierung eine schnelle Sortierung durchführen, wenn die Daten sortiert sind. Oder wenn wir etwas über die zu sortierenden Gegenstände wissen, können wir es wahrscheinlich besser machen.

Dies kann Ihre Frage nicht direkt beantworten, dachte ich würde meine zwei Cent hinzufügen.

Heap Sort ist eine sichere Sache, wenn Sie mit sehr großen Eingaben arbeiten. Eine asymptotische Analyse zeigt, dass die Reihenfolge des Wachstums von Heapsort im schlimmsten Fall Big-O(n logn)besser ist als die von Quicksort im Big-O(n^2)schlimmsten Fall. Allerdings Heapsort in der Praxis auf den meisten Maschinen etwas langsamer als eine gut implementierte schnelle Sortierung. Heapsort ist auch kein stabiler Sortieralgorithmus.

Der Grund, warum Heapsort in der Praxis langsamer ist als Quicksort, liegt in der besseren Referenzlokalität (" https://en.wikipedia.org/wiki/Locality_of_reference ") in Quicksort, wo sich Datenelemente in relativ engen Speicherorten befinden. Systeme mit starker Referenzlokalität sind hervorragende Kandidaten für die Leistungsoptimierung. Die Heap-Sortierung befasst sich jedoch mit größeren Sprüngen. Dies macht Quicksort für kleinere Eingänge günstiger.

Für mich gibt es einen sehr grundlegenden Unterschied zwischen Heapsort und Quicksort: Letzteres verwendet eine Rekursion. In rekursiven Algorithmen wächst der Heap mit der Anzahl der Rekursionen. Dies spielt keine Rolle, wenn n klein ist, aber im Moment sortiere ich zwei Matrizen mit n = 10 ^ 9 !!. Das Programm benötigt fast 10 GB RAM und jeder zusätzliche Speicher veranlasst meinen Computer, auf den Speicher der virtuellen Festplatte zu wechseln. Meine Festplatte ist eine RAM-Festplatte, aber das Wechseln zu ihr macht einen großen Unterschied in der Geschwindigkeit . In einem in C ++ codierten Statpack, das einstellbare Dimensionsmatrizen enthält, deren Größe dem Programmierer im Voraus unbekannt ist, und eine nichtparametrische statistische Sortierung, bevorzuge ich den Heapsort, um Verzögerungen bei der Verwendung mit Matrizen mit sehr großen Datenmengen zu vermeiden.

Um die ursprüngliche Frage zu beantworten und einige der anderen Kommentare hier anzusprechen:

Ich habe gerade Implementierungen von Auswahl, Schnell, Zusammenführen und Heap-Sortierung verglichen, um zu sehen, wie sie sich gegeneinander stapeln würden. Die Antwort ist, dass sie alle ihre Nachteile haben.

TL; DR: Schnell ist die beste Allzweck-Sortierung (relativ schnell, stabil und meistens vorhanden). Ich persönlich bevorzuge jedoch die Heap-Sortierung, es sei denn, ich benötige eine stabile Sortierung.

Auswahl - N ^ 2 - Es ist wirklich nur für weniger als 20 Elemente oder so gut, dann ist es übertroffen. Es sei denn, Ihre Daten sind bereits sortiert oder sehr, sehr nahe. N ^ 2 wird sehr langsam, sehr schnell.

Schnell ist meiner Erfahrung nach nicht immer so schnell. Boni für die Verwendung der schnellen Sortierung als allgemeine Sortierung sind jedoch, dass sie relativ schnell und stabil ist. Es ist auch ein In-Place-Algorithmus, der jedoch im Allgemeinen rekursiv implementiert wird und zusätzlichen Stapelspeicherplatz beansprucht. Es liegt auch irgendwo zwischen O (n log n) und O (n ^ 2). Das Timing einiger Arten scheint dies zu bestätigen, insbesondere wenn die Werte in einem engen Bereich liegen. Es ist viel schneller als die Auswahlsortierung für 10.000.000 Elemente, aber langsamer als das Zusammenführen oder Haufen.

Die Zusammenführungssortierung ist garantiert O (n log n), da ihre Sortierung nicht datenabhängig ist. Es macht einfach das, was es macht, unabhängig davon, welche Werte Sie ihm gegeben haben. Es ist auch stabil, aber sehr große Sorten können Ihren Stack ausblasen, wenn Sie bei der Implementierung nicht vorsichtig sind. Es gibt einige komplexe Implementierungen für die Sortierung an Ort und Stelle, aber im Allgemeinen benötigen Sie in jeder Ebene ein anderes Array, um Ihre Werte zusammenzuführen. Wenn diese Arrays auf dem Stapel gespeichert sind, können Probleme auftreten.

Die Heap-Sortierung ist max. O (n log n), in vielen Fällen jedoch schneller, je nachdem, wie weit Sie Ihre Werte auf dem log n-tiefen Heap nach oben verschieben müssen. Der Heap kann problemlos direkt im ursprünglichen Array implementiert werden, benötigt also keinen zusätzlichen Speicher und ist iterativ, sodass Sie sich keine Sorgen über den Stapelüberlauf beim Rekursieren machen müssen. Der große Nachteil der Heap-Sortierung ist, dass es sich nicht um eine stabile Sortierung handelt, was bedeutet, dass es richtig ist, wenn Sie das brauchen.