Quicksort - Problem



  • SortierFachmann schrieb:

    aber wehe, QuickSort erwischt als Pivot-Element mal etwas zu oft einen Wert,
    der weit weg vom Durchschnittswert liegt! dann ist sogar bubble sort besser als
    QuickSort

    Das "etwas zu oft" sollte man quantifizieren. Meiner Erinnerung nach ist es kein Problem, wenn Quicksort mit einer Wahrscheinlichkeit von 0,9 das ungünstigste Pivotelement erwischt. Das Problem ist einfach, dass die meisten Sortieranwendungen auf fast vorsortierten Daten stattfinden.

    heap sort ist eine [...] MergeSort Variante

    Wow, so hab ich das noch gar nicht gesehen. Made my day. 👍



  • Bashar schrieb:

    SortierFachmann schrieb:

    aber wehe, QuickSort erwischt als Pivot-Element mal etwas zu oft einen Wert,
    der weit weg vom Durchschnittswert liegt! dann ist sogar bubble sort besser als
    QuickSort

    Das "etwas zu oft" sollte man quantifizieren. Meiner Erinnerung nach ist es kein Problem, wenn Quicksort mit einer Wahrscheinlichkeit von 0,9 das ungünstigste Pivotelement erwischt. Das Problem ist einfach, dass die meisten Sortieranwendungen auf fast vorsortierten Daten stattfinden.

    Vorsortierte Daten sind super für Quicksort, wenn man den Pivot mit z.B. Median of 3 auswählt.
    Es zwingt einen ja keiner die problematische Variante mit Pivot = erstes Element zu implementieren.



  • hustbaer schrieb:

    SortierFachmann schrieb:

    (komisches Getrolle)

    Dass Merge-Sort im average case schneller (oder auch nur gleich schnell) sein soll als Quicksort ist purer Unfug.
    Dass Quicksort dafür worst case schlecht aussieht ist unbestritten.
    Deswegen verwendet man ihn ja auch nicht alleine.

    Heutzutage arbeitet man aber auch kaum noch mit Single-Core Prozessoren, sondern
    verteilt größere Jobs auch gerne mal auf mehrere physische CPUs. Jetzt erklär
    mir mal bitte, wie QuickSort seine beiden Listen gleichzeitig sortieren
    und dabei die zur Verfügung stehende Zeit auch optimal ausnutzen soll, wenn
    Liste 1 10 Einträge und Liste 2 100000 Einträge enthält. CPU1 ist mit seiner
    Teilliste fertig und darf dann mal ein paar Stunden darauf warten, bis
    CPU2 mit der 10000x größeren Liste fertig ist. Tja, so sehen wohl die
    Laufzeit-Effizienz Vorstellungen von Prof. hustbaer und Dr. Bashar aus.
    Zum Glück gibt's noch andere kompetente Programmierer da draußen, die
    zunehmend QuickSort in die Tonne kippen, weil's einfach nicht mehr zeitgemäß
    ist auf nem Multicore (wegen der inferioren Laufzeiteffizienz). Ganz zu
    schweigen vom Super-GAU-Potential, wenn QuickSort mal eine Pechsträhne
    beim Pivot-Pokern haben sollte.

    MergeSort hat gar keinen worst case oder best case, sondern einfach nur einen
    average case, der sogar theoretisch immer schneller sein muss als
    jeder noch so günstige best case-Verlauf von QuickSort. Hat der Professor
    damals Länge mal Breite bewiesen, also muss es wohl so sein.
    Sogar auf dem SingleCore.
    Nur wegen der schnellen inneren Schleife kann QuickSort diesen
    theoretischen Nachteil in der physischen Realität kompensieren, verliert
    aber gegenüber MergeSort spätestens dann massiv an Boden, wenn man die
    stets gleich großen Listen von MergeSort auf mehrere CPUs verteilen kann
    (während die 5%-links, 95%-rechts Listen von QSort nicht gerade optimal
    dazu geeignet sind!)

    So, jetzt haste mal wieder was gelernt, Prof. hustbaer
    C & D



  • Warum so gehässig? Warst du schon so, bevor du Sortierfachmann wurdest?



  • Er hat wahrscheinlich einen kleinen Penis.



  • Lieber Herr Prof. Dr. Dr. SortierFachmann,

    Parallelisierbarkeit ist nun wieder ein ganz eigenes Thema.

    Wenn man auf geringe Latenz optimieren will, und dafür schlechteren Throughput in kauf nimmt, dann wird es Sinn machen einen parallelen Merge-Sort zu verwenden. Vorausgesetzt man hat mehr als 2 CPUs, denn mit nur 2 CPUs wird Introsort vermutlich auch noch besser abschneiden.

    Wenn man dagegen auf Throughput optimieren will, was jetzt nicht gerade ein seltener Fall ist, dann wird es wohl mehr Sinn machen einen (parallelen oder auch nicht) Introsort zu verwenden.

    @Bashar:

    Bashar schrieb:

    Warum so gehässig?

    Weil er Student ist, und meint die Weisheit mit dem Löffel gefressen zu haben.



  • Irgendwer schrieb:

    Er hat wahrscheinlich einen kleinen Penis.

    👍 👍 👍 hihi^^

    er hat penis gesagt hihi^^



  • 314159265358979 schrieb:

    [...]Mergesort[...]weil kein zusätzlicher Speicher benötigt wird, ein splicen reicht 😉

    Ganz ohne zusätzlichen Speicher kommt man da nicht aus. Du brauchst O(log n) zusätzlichen Speicher für Mergesort. Rekursiv implementiert, wird O(log n) Speicher vom "Stapel" verwendet. Iterativ gibt's den Algorithmus auch. Dann brauchst Du aber immer noch O(log n) temporäre Listen, zwischen denen Du hin und her "splicen" musst. libstd++ hat zB std::list<>::sort iterativ implementiert und legt zwischenzeitlich ein lokales Array von 64 Listen an. Das reicht zum Sortieren für ca pow(2,64) Elemente. 😉

    Aber wenn man nicht gerade auf Listen arbeitet, sondern auf "Arrays", sehe ich nicht, wie man Mergesort ohne mindestens 50% Overhead (Speicherverbrauch bezogen auf das ursprüngliche Array) erledigen kann.



  • hustbaer schrieb:

    wxSkip schrieb:

    EDIT:

    hustbaer schrieb:

    Wikipedia schrieb:

    Introsort or introspective sort is a sorting algorithm designed by David Musser in 1997. It begins with quicksort and switches to heapsort when the recursion depth exceeds a level based on (the logarithm of) the number of elements being sorted.

    D.h. so lange Introsort nicht umschaltet *ist* es ein Quicksort. Der minimale Overhead die Rekursionstiefe mitzuzählen fällt dabei wirklich nicht ins Gewicht.

    Jetzt klar?

    Hey, genau so habe ich das auch "erfunden", inklusive logarithmischer Berechnung 🙂 . Und dort liegt eben auch der Unterschied in der Geschwindigkeit von Introsort.

    Bist du sicher?
    Bei den allermeisten Inputs schaltet std::sort nämlich nicht um.

    Könnte auch daran liegen wie du das Pivot Element ermittelt hast (üblich ist "Median of 3 Medians of 3"), bzw. wann du für kleine Mengen auf Insertion-Sort umgeschaltet hast.

    Aha, doch falsch verstanden 😉

    Am Pivotelement liegt es nicht, beim Durchschnitt aus 2 oder 3 Elementen ist es bei mir ziemlich genau gleich schnell.

    @SortierFachmann: Dann erklär mir doch mal, was dich daran hindert, nachdem Thread 1 mit der 10-Elemente-Liste fertig ist, die zwei Teile aus der 100000-Elemente-Liste wieder auf 2 Threads aufzuteilen? Ich glaube nicht, dass der Zeitraum, der benötigt wird, um einen Thread zu erstellen, so groß ist, dass Mergesort da schneller wird.


Anmelden zum Antworten