Diskussion:Quicksort
Füge neue Diskussionsthemen unten an:
Klicke auf , um ein neues Diskussionsthema zu beginnen.
| Auf dieser Seite werden Abschnitte ab Überschriftenebene 2 automatisch archiviert, die seit 30 Tagen mit dem Baustein {{Erledigt|1=--~~~~}} versehen sind. |
| Archiv |
| Zur Archivübersicht |
| Wie wird ein Archiv angelegt? |
Ist Quicksort wirklich schneller? Bearbeiten
Mal angenommen, man hätte acht Elemente. Bubblesort würde hierfür ca. 7+6+5+4+3+2+1 Datenzugriffe brauchen (das sind 28). (Fange hinten an und vertausche, wenn das hintere Element größer, dann wiederhole dasselbe mit immer einem Element weiter hinten als Ziel, bis beim hintersten). Quicksort muß erst das mittlere Element(ein Zufälliges geht wohl langsamer) finden. Läuft es einmal über alle Elemente. Sind acht Zugriffe. Anschließend schiebt es in der linken und in der rechten Hälfte die Zeiger immer dann vor, wenn sie links kleiner oder rechts größer sind wie das Mittlere. Ist das nicht der Fall, vertauscht es beide Elemente. Das braucht auch acht Datenzugriffe. Geschweige denn, es geht nicht, dann muß es unter Umständen die Elemente in einem Array verschieben. Das braucht. Dann ruft sich Quicksort im Idealfall mit den vier linken und vier rechten Elementen selber auf und macht mit diesen dasselbe, wieder 16 Zugriffe. Dann ruft es in den Vieregruppen sich nochmal selber auf und vertauscht gegebenenfalls die Elemente. Das könnte man mit acht Zugriffen hinbringen. Macht also insgesamt vierzig Zugriffe. Findet man also nicht mit einer gescheiten Heuristik das mittlere Element, ist Bubblesort genauso schnell? Ich habe das nie richtig kapiert. Das es geht, ist klar. Die Frage ist nur wie schnell. Gehe davon aus, daß die Daten in einem Array vorliegen. Man könnte natürlich auch separierte Datensätze absteigend mit einer Kennzeichnung versehen, wie weit nach links sie zu sortieren sind. Aber da dann wieder drin rumzusuchen, braucht auch. (nicht signierter Beitrag von 87.143.92.68 (Diskussion) 06:01, 14. Jul 2016 (CEST))
- Bubblesort ist in und Quicksort im "Normalfall" in ist damit im "Normalfall" deutlich schneller für größe n, d.h. für große Datensätze. Bei sehr ungünstigen Datensätzen, die zu einer konstant schlechten Pivotwahl führen, kann der einfache Quicksortalgorithmus auch in liegen, in diesem Fall ist der Bubblesort dann in der Tat genauso schnell.
- Allerdings besagt diese Asymptotik nichts für kleine Datensätze und es kommt durchaus vor, dass "schnelle" (Sortier)algorithmen auf kleinen Datensätzen langsamer arbeiten als (einfachere) "langsame" Algorithmen. Manche optimierten Implementierungen kombinieren daher die Algorithmen, dann wird auf den großen Datensatz zunächst ein schneller rekursiver nlog(n)-Algorithmus angewandt. Wenn bei dessen Bearbeitungsschritten der Datensatz sehr klein geworden ist (im Normalfall n im einstelligen Bereich), greift die Implementierung zu einem anderen Sortierverfahren, das für diesen kleinen Datensatz schneller ist. Siehe dazu z.B. Introsort. Es lohnt sich übrigens auch immer einen Blick auf die englischen Artikel zu werfen, die derzeit oft etwas ausführlicher sind und zusätzliche Infos enthalten.--Kmhkmh (Diskussion) 08:03, 14. Jul. 2016 (CEST)
Fehler im Pseudocode Bearbeiten
Im Vergleich zur englischen Seite unterscheidet sich der Pseudocode der Hauptfunktion.
Die englischen Version sieht (übertragen) so aus:
funktion quicksort(links, rechts)
falls links < rechts dann
teiler:= teile(links, rechts)
quicksort(links, teiler)
quicksort(teiler+1, rechts)
ende
ende
Die Deutsche so:
funktion quicksort(links, rechts)
falls links < rechts dann
teiler:= teile(links, rechts)
quicksort(links, teiler-1)
quicksort(teiler+1, rechts)
ende
ende
Der feine Unterschied ist das "teiler-1" vs "teiler".
Das führt in der deutschen Version zu teilweise falscher Sortierung. Die Englische scheint richtig so sein.
- -Ich denke, "teiler-1" sollte richtig sein, da der Wert an der Teilerposition schon an der richtigen Stelle ist und nicht mehr sortiert zu werden braucht. Ich finde aber auch, dass der Algorithmus nicht korrekt sortiert, z. B. bei der Zahlenfolge 4, 3, 5. Mein Vorschlag wäre, die i-Schleife bis "rechts" und nicht bis "rechts-1" laufen zu lassen. ---Stan-MS (Diskussion) 14:37, 28. Mär. 2019 (CET)
Neuer Weblink Bearbeiten
Ich wollte meine Seite mit animierten Darstellungen von Quicksort (http://www.chrislaux.com/de/quicksort.html) für die Weblinks Sektion anbieten. Die Erklärungen sind dort alle auf Deutsch und die Animationen ergänzen den Text dieser Wikipedia-Seite gut.
--Ctlaux (Diskussion) 21:22, 3. Sep. 2019 (CEST)
- Ich sehe nicht was gegen einen Eintrag im Abschnitt Weblinks sprechen würde. Also nur zu.--Kmhkmh (Diskussion) 23:17, 3. Sep. 2019 (CEST)
Vermeidung Speicherplatz für Rekursion Bearbeiten
Ich überblick' das im Moment nicht ganz, aber ich habe das Gefühl, dass einige der Methoden, die Rekursionstiefe möglichst "garantiert" auf O(log n) zu beschränken, als Auswirkung haben können, dass man sich im Gegenzug wieder einhandelt, im Worst Case mit einer Laufzeit von O(n²) dazustehen.
Unverständlicher Satz Bearbeiten
Im Abschnitt Quicksort#Iteratives Quicksort heißt es: "Eine solche Liste sortiert Insertionsort in linearer Zeit". Wie kann Insertionsort für kleine Listengrößen linearen Aufwand haben? Dabei ist doch allgemeinbekannt, dass Insertionsort in liegt. --141.30.247.160 21:01, 8. Feb. 2023 (CET)
- Vermutlich bezieht sich das auf bestimmte Listen (die beim Quicksort das worst case Verhalten auslösen können) und nicht auf den allgemeinen Fall. anders ausgedrückt der Quicksort erzeugt Teillisten, die der Insertionsort in linearer Zeit sortieren kann. <math>\mathcal{O}( n^2 ) ist ja nicht das Laufzeitverhalten des Insertionsorts bei jedem Datensatz, eine Liste in umgekehrter Reihenfolge sortiert der Insertionsort z.B. in linear Zeit (da er zum korrekten Einfügen immer nur einen Vergleich benötigt).--Kmhkmh (Diskussion) 14:39, 24. Feb. 2023 (CET)
Aneinander Vorbeilaufen der Indizes Bearbeiten
Sollte es mit dem gegebenen Pseudocode nicht unmöglich sein, dass die Indizes i und j aneinander vorbeilaufen wie in den Beispielen?
Z.B. beim einbeispiel Beispiel läuft nach ein paar Schritten das i bis zum p an achter Stelle. Sagen wir mal, das sei index 8 also i = 8. Nach der Schleife, die i nach rechts laufen lässt, folgt eine, die j nach links laufen lässt. Nun ist j vom Schritt vorher bereits gleich 9. 9 ist größer als 8 und s ist größer als l, also wird j:=8 und zeigt nun genau wie das i auf's p. Jetzt ist allerdings j nicht mehr größer als i und somit endet die Schleife, ohne dass die Indizes aneinander vorbeilaufen. --77.6.72.193 10:28, 13. Mai 2023 (CEST)
- ja, die Kommentare im Code und das Beispiel darunter sind falsch, bei "links < rechts" vorausgesetzt, kann man ziemlich einfach zeigen, daß die Invariante i <= j in der großen Schleife und nach Ende der großen Schleife gilt. --195.243.100.252 13:46, 10. Jan. 2024 (CET)
Quicksort in funktionalen Sprachen in der Regel nicht in-place Bearbeiten
Das beschriebene Sortierverfahren im Abschnitt "Quicksort in funktionalen Sprachen" ist nicht Quicksort. Es ist kein in-place-Sortierverfahren, da neue Listen erstellt werden, die anschließend konkateniert werden. Das liegt in der Natur von funktionalen Sprachen, die ja gerade versuchen, veränderliche Zustände zu vermeiden. Quicksort ist aber definitiv ein in-place-Verfahren, was bereits im ersten Absatz erwähnt wird: "... und dass er, abgesehen von dem für die Rekursion zusätzlichen benötigten Platz auf dem Aufruf-Stack, ohne zusätzlichen Speicherplatz auskommt." Im Abschnitt "Speicherplatz" wird es auch nochmal explizit erwähnt: "Quicksort ist ein in-Place-Verfahren." Meines Wissens gibt es keine einfache, funktionale Implementierung von Quicksort.
Quicksort ist zudem ein "nicht-stabiler Sortieralgorithmus". Das ist ebenfalls charakteristisch für Quicksort, er ist daher für stabiles sortieren ungeeignet. Das angegebene Haskell-Programm lässt sich jedoch leicht ändern, so dass es stabil sortiert. Dazu muss lediglich in der letzten Zeile der Vergleich beim Erzeugen der neuen Listen geändert werden (aus "<=" wird "<", aus ">" wird ">="):
quicksort (e:es) = quicksort [x | x <- es, x < e] ++ [e] ++ quicksort [x | x <- es, x >= e]
Der ganze Abschnitt gehört meines Erachtens entfernt, da er einen anderen Algorithmus beschreibt. --KamikazeJones (Diskussion) 00:29, 2. Jan. 2024 (CET)