Warum Quicksort?
-
Hi there!
Mein Prof. meinte heute, Quicksort sei der in der Praxis am meisten eingesetzte Sortieralgorithmus. Gleichzeitig sagte er bei der Vorlesung aber auch, Quicksort sei im worst case O(n^2) und benoetigt mehr Speicher als z. B. ein Heapsort (der nebenbeibemerkt lt. VL im worst case ebenfalls O(n log n) Zeitkomplexitaet hat). Warum wird dann Quicksort so gern/oft verwendet, wo es doch Sortieralgorithmen gibt, die anscheinend schneller sind?
-
Weil, so denke ich, Quicksort ganz gut im "Mid-Case" ist.. Man kann ja auch nicht immer vom worst-case ausgehen, und vielleicht quicksort > heapsort im mid-case..
-
Na weil der Worst-Case und damit die quadr. Abhängigkeit eben recht selten eintritt.
Daher liegt man im allgemeinen Fall mit Quicksort ganz gut.
-
Warum nimmt man nen binären Suchbaum wenn er eh zuner linearen Liste verkommen kann?!?!
-
Heapsort wird durchaus auch sehr oft verwendet. Er ist nämlich stable und hat ne Speicherkomplexität von O(1). Im Java API ist sort() derzeit (und schon immer) über Heapsort implementiert.
-
Optimizer schrieb:
Heapsort wird durchaus auch sehr oft verwendet. Er ist nämlich stable und hat ne Speicherkomplexität von O(1). Im Java API ist sort() derzeit (und schon immer) über Heapsort implementiert.
Unsinn. Guck mal in die Java-API-Doku. Da steht zum Beispiel folgendes:
public static void sort(byte[] a)
Sorts the specified array of bytes into ascending numerical order. The sorting algorithm is a tuned quicksort, adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993). This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance.
-
@Optimizer
Welches sort meinst du genau?
imho wird für Arrays.sort( Object [] ) laut JDK
ein mergesort verwendet. Außerdem scheint ein
aufgemotztes quiksort für primitive Datentypen
verwendet zu werden.
-
Jo hab mich geirrt. Es ist ein Mergesort.
@Gregor: Dass für primitive Quicksort verwendet wird, war mir schon klar, weil stable da kein Thema ist.
-
Optimizer schrieb:
@Gregor: Dass für primitive Quicksort verwendet wird, war mir schon klar, weil stable da kein Thema ist.
Ja, da hast du wohl Recht!
-
afaik hat Quicksort snne tolle kleine innere Schleife, die paßt in jeden Cache und der Compiler kann gut optimieren. Deswegen ist quicksort auch so beliebt.
-
Man kann Quicksort (statistisch gesehen) auch im Worst-Case ruppzupp auf n*log n bringen, indem man die Wahl des Pivot-Elements dem Zufall überlässt (Randomized Quicksort).
Ansonsten sind Merge-, Shell- und Heap-Sort oft die bessere Wahl, da sie wie gesagt stable sind.
Für kleine Arrays oder bei extrem langsamem Zugriff kann InsertSort die bessere Wahl sein.
-
Sgt. Nukem schrieb:
Man kann Quicksort (statistisch gesehen) auch im Worst-Case ruppzupp auf n*log n bringen, indem man die Wahl des Pivot-Elements dem Zufall überlässt (Randomized Quicksort).
und für praktische belange macht man median-of-three.
Ansonsten sind Merge-, Shell- und Heap-Sort oft die bessere Wahl, da sie wie gesagt stable sind.stable oder nicht ist fast immer doch egal. wenn ich kein stable brauche, nehme ich doch nicht stable, denn stable macht bei quicksort langsamer.
die innere schleife ist wirklich extrem einfach. besonders, wenn man die sedgewick-optimierung nimmt.
Für kleine Arrays oder bei extrem langsamem Zugriff kann InsertSort die bessere Wahl sein.
ja, deswegen läßt man die rekursion von quicksort nur bis zu größen von 20 oder 50 gehen und macht die kleinen dann mit insertion sort.
oder genauer, man läßt die rekursion nur bis 20 oder 50 gehen und belößt das array im quicksortlauf so. also man macht ne ungenaue vorsortierung. und dann jagt man das ganze durch insertion sort.
gegen das einbrechen von quicksort (mit median of three muß man schon konstruierte fälle haben (die leider in der prakis sogar vorkommen)), überwacht man die rekursionstiefe und wenn's zu tief wird, schaltet man um auf heapsort oder was anderes, was nicht einbricht.
um zur ausgangsfrage zurückzukommen, quicksort ist am schnellsten, deswegen nimmt man es. nicht nur die innere schleife ist sehr fein, es passieren auch wenige sehr vertauschungen.
-
volkard schrieb:
Ansonsten sind Merge-, Shell- und Heap-Sort oft die bessere Wahl, da sie wie gesagt stable sind.stable oder nicht ist fast immer doch egal. wenn ich kein stable brauche, nehme ich doch nicht stable, denn stable macht bei quicksort langsamer.
Klar, es war auch gemeint, wenn stable GEBRAUCHT wird (bzw. besser wäre).
Ansonsten natürlich Humbug.
-
Sgt. Nukem schrieb:
Man kann Quicksort (statistisch gesehen) auch im Worst-Case ruppzupp auf n*log n bringen, indem man die Wahl des Pivot-Elements dem Zufall überlässt (Randomized Quicksort).
Nee. Die Laufzeit hängt vom Zufall ab und der Erwartungswert ist n*log(n). (das ist kein Worst-Case, auch nicht statistisch gesehen [was auch immer das bedeuten mag]). Entspricht genau der Average-Case Laufzeit vom deterministischen QS aber im randomisierten kann es doch auch zu quadratischem Aufwand kommen.
Der Vorteil ist imho ein anderer. Bei der Analyse des Average-Case nimmt man beim deterministischen Quicksort an, dass jede Permutation des Eingabearrays gleichwahrscheinlich ist. Dies ist in der Praxis nicht immer der Fall wodurch man mit schlechterer Laufzeit zu rechnen hat. Durch die Zufallswahl des Pivots wird dieses Manko beseitigt.