Diskussion:Quicksort

Diese Diskussionsseite dient dazu, Verbesserungen am Artikel „Quicksort“ zu besprechen. Persönliche Betrachtungen zum Thema gehören nicht hierher. Für allgemeine Wissensfragen gibt es die Auskunft.

Füge neue Diskussionsthemen unten an:

Klicke auf Abschnitt hinzufügen, um ein neues Diskussionsthema zu beginnen.

• Diskussionsregeln
• Hilfe zu Diskussionsseiten
• Sei sachlich und freundlich!
• Greife niemanden persönlich an!
• Geh von guten Absichten aus.

Automatische Archivierung

Auf dieser Seite werden Abschnitte automatisch archiviert, deren jüngster Beitrag mehr als 360 Tage zurückliegt und die mindestens 3 signierte Beiträge enthalten.

Automatische Archivierung

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?

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 $O(n^{2})$ und Quicksort im "Normalfall" in $O(nlog(n))$ 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 $O(n^{2})$ 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

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

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

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.

--arilou (Diskussion) 18:08, 26. Nov. 2020 (CET)

Unverständlicher Satz

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 ${\mathcal {O}}(n^{2})$ 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

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

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)

Das "richtige" Quicksort ist strenggenommen zwar auch nicht in-place, aber abgesehen davon hast du Recht. Was häufig als Implementierung von Quicksort in funktionalen Sprachen beworben wird, ist kein Quicksort. Es illustriert aber einigermaßen gut einen großen Teil der grundlegenden Idee. Ich lösche trotzdem mal. --Daniel5Ko (Diskussion) 01:51, 26. Jul. 2024 (CEST)

Letztlich ist das ein Frage was in der reputablen Referenzliteratur als Quicksort bezeichnet wird, Welche Publikation den "richtigen" oder "echten" Quicksort beschreibt kann Wikipedia nicht entscheiden. Stattdessen gehört ist alles was in der Referenzliteratur als Quicksort bezeichnet wird auch bei uns Quicksort, allerdings müssen natürlich unterschiedliche Eigenschaften der unterschiedlichen Variationen erwähnt werden.--Kmhkmh (Diskussion) 10:53, 26. Jul. 2024 (CEST)

Ganz toller Beitrag. Statt zu entscheiden, was das "wirkliche" Quicksort ist, müssen wir also nur entscheiden, was "reputable" Publikationen sind. Das ist recht sinnlos, und ich denke, man sollte hier im Normalfall relativ strikt vorgehen.

Von dieser Problematik abgesehen, stand der bemängelte und nun gelöschte Text jedoch unter der Überschrift "Varianten" (und das war auch schon so, als KamikazeJones seinen Beitrag verfasst hat), wodurch man natürlich auch milder urteilen könnte. --Daniel5Ko (Diskussion) 03:38, 27. Jul. 2024 (CEST)

Ja, so "toll", dass es eine Projektvorgabe ist ("strikt" nach Literatur vorzugehen).--Kmhkmh (Diskussion) 04:10, 27. Jul. 2024 (CEST)