Diskussion:Quicksort
Füge neue Diskussionsthemen unten an:
Klicke auf , um ein neues Diskussionsthema zu beginnen, und unterschreibe deinen Beitrag bitte mit
oder --~~~~.
| Auf dieser Seite werden Abschnitte ab Überschriftebene 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 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
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)
Das Pivotelement MUSS IMMER das mittlere sein
Ich beschäftige mich praktisch bereits mein ganzes Leben lang mit Sortierverfahren und möchte im Zusammenhang mit Quicksort einmal auf etwas Grundsätzliches hinweisen: Bei vielen Stellen, wo die Funktionsweise von Quicksort erklärt wird, wird die Sache so dargestellt, dass man in einer Rekursion praktisch jedes Element als Pivotelement verwenden kann. Das ist aber falsch! Entsprechend der Grundidee von "Teile und Herrsche", muss man nämlich IMMER das mittlere Element als Pivotelement verwenden, weil es ansonsten zum Absturz von Quicksort kommen kann. Ursache: Die Anzahl der gleichzeitig aktiven Rekursionen, die natürlich begrenzt ist, kann ansonsten mit der Anzahl der zu sortierenden Elemente identisch sein.
Beispiel:
Es gibt 5001 zu sortierende Zahlen / Datensätze. Wenn der Best-Case (1,2,3,...) oder der Worst-Case (...,3,2,1) vorliegt, dann wird es in der Programmiersprache "Visual Basic" unweigerlich immer zum Absturz von Quicksort kommen, wenn man in beiden Fällen das erste oder letzte Element als Pivotelement verwendet. Die Anzahl der gleichzeitig aktiven Rekursionen, ist bei "Visual Basic" nämlich auf 5000 begrenzt.
Lösung für das Problem:
1. Vertausche das mittlere Element mit dem letzten.
2. Mache das letzte Element zum Pivotelement.
3. Verschiebe alle kleineren Elemente zum Anfang der Rekursion.
4. Vertausche das Element rechts neben dem kleineren Bereich mit dem Pivotelement.
5. Hänge im rechten Bereich alle mit dem Pivotelement identisch großen Elemente, an das Pivotelement an.
Mit freundlichen Grüßen: Martin Oppermann --77.22.103.82 20:49, 27. Jan. 2022 (CET)
- Begrenzungen bestimmter Programmiersprachen sind nicht relevant für die allgemeine Beschreibung eines Sortierverfahrens.
- Wie jeder Informatiker in seinem Studium lernt, ist bei jedem rekursiven Verfahren darauf zu achten, dass das zu lösende Problem mit jeder Rekursionsstufe garantiert kleiner wird.
Dies kann bei Quicksort auf verschiedene Weise erreicht werden; beispielsweise indem bei der Unterteilung das Pivotelement nicht in den beiden "Unterhälften" mitsortiert wird. Dadurch ist der schlimmste Fall: Die eine Unterhälfte ist leer, die andere enthält "alles minus 1 Element", womit das Problem mindestens 1 Element kleiner wurde. - Afaik gibt es für Quicksort verschiedene Methoden der Wahl eines Pivotelements, die alle garantiert funktionieren, und ja, einfach irgend eines zu nehmen, kann dennoch garantiert funktionieren ~ vielleicht nicht "gut", aber "funktioniert".
- --arilou (Diskussion) 09:24, 28. Jan. 2022 (CET)
Kritik am Pseudocode
Ich bin zwar zugegeben kein Experte für Pseudocodes und habe davon nicht so viel Ahnung, aber selbst wenn Pseudocodes nur oberflächlich eine Funktionsweise beschreiben sollen, selbst dann sollte man den Pseudocode im Artikel vielleicht gegen einen anderen ersetzen, den man 1:1 in einen funktionsfähigen Quellcode umwandeln kann. Das Problem besteht meiner Ansicht nach nämlich darin, dass man bei Quicksort zu viel falsch machen kann. Insbesondere bei den Varianten, wo sich "i" und "j" aufeinander zubewegen. Wenn man etwas falsch macht, dann kann es passieren, dass "i" nach der Teilung einmal dort steht, wo der Bereich >= Pivot beginnt und ein anderes Mal steht "i" auf dem letzten Element, das kleiner als Pivot ist, was dann unweigerlich zu einer fehlerhaften Sortierung führt. Es kann sogar zu Endlosschleifen kommen, aus denen Quicksort dann nicht mehr herauskommt. Ebenfalls problematisch ist die Situation, wenn es keine Elemente gibt, die kleiner als Pivot sind. Daher mein Vorschlag einen funktionsfähigen Pseudocode zu verwenden, weil der im Artikel - wie ich getestet habe - nicht funktionsfähig ist.
Was ebenfalls sehr oft in Artikeln / Dokumentationen / Erklärungen und Videos über Quicksort zu sehen ist, dass das letzte Element als Pivot verwendet wird. Das ist aber falsch und man darf das unter keinen Umständen machen! Quicksort basiert ja auf dem Prinzip von "teile und herrsche" und demzufolge teilt man immer in der Mitte. Für Pivot muss man also immer das mittlere Element verwenden. Andernfalls kann Quicksort nämlich abstürzen, wenn die maximale Anzahl der gleichzeitig aktiven Rekursionen überschritten wird. Kritisch sind hierbei die Situationen des Best-Case (1,2,3,...), des Worst-Case (...,3,2,1), sowie wenn alle Elemente identisch sind, weil bei Quicksort die maximale Anzahl der gleichzeitig aktiven Rekursionen, dann mit der Anzahl der zu sortierenden Elemente identisch ist. Bei "Visual Basic" führt dies unter Excel in allen drei Fällen dann unweigerlich zum Stapelüberlauf der Rekursionen, wenn es mehr als 2748 zu sortierende Elemente gibt. --31.17.34.192 18:26, 18. Apr. 2022 (CEST)
funktionsfähiger Pseudocode
Hier mein Vorschlag für einen funktionsfähigen einteiligen Pseudocode:
funktion quicksort(links, rechts)
i := links
j := rechts - 1
pivot := links + Int[[rechts - links + 1] / 2]
// Das Element "pivot" mit dem Letzten vertauschen
falls pivot < rechts dann
tausche daten[pivot] mit daten[rechts]
ende
pivot := daten[rechts]
wiederhole solange i < j
// Der Anfang ist kleiner als Pivot
falls i < rechts und daten[i] < pivot dann
i := i + 1
ende
// Das Ende ist größer oder gleich als Pivot
falls links < j und daten[j] >= pivot dann
j := j - 1
ende
// Wenn zutreffend, den Anfang und das Ende vertauschen
falls i < j und daten[i] >= pivot und daten[j] < pivot dann
tausche daten[i] mit daten[j]
ende
ende
// Eine eventuelle fehlerhafte Position von "i" korrigieren
falls daten[i] < pivot dann
i := i + 1
ende
// Das Element "i" mit "pivot" vertauschen
falls i < rechts dann
tausche daten[i] mit daten[rechts]
ende
// Wenn zutreffend, die Rekursion "kleiner als..." starten
falls links < i - 1 dann
starte funktion quicksort(links, i - 1)
ende
// Wenn zutreffend, die Rekursion "größer als..." starten
falls i + 1 < rechts dann
starte funktion quicksort(i + 1, rechts)
ende
ende
--31.17.34.192 18:26, 18. Apr. 2022 (CEST)
Variante mit zwei aufeinanderfolgenden Schleifen
Hier noch ein weiterer Pseudocode, mit zwei aufeinanderfolgenden Schleifen. Er ist zwar fast immer deutlich langsamer, kann in Sonderfällen aber auch deutlich schneller arbeiten. Schneller insbesondere dann, wenn es viele Elemente gibt, die jeweils mehrfach vorhanden sind. Das normale Quicksort würde bei den Zahlen 4,8,4,1,4,7,4,3,4 nach der Teilung das Ergebnis 3,1,4,8,4,7,4,4,4 liefern und von Element 1 bis 2 die nächste linke und von Element 4 bis 9 die nächste rechte Rekursion starten. Der folgende Pseudocode liefert hingegen das Ergebnis 1,3,4,4,4,4,4,8,7 und startet ebenfalls Element 1 bis 2 als die nächste linke, aber nur Element 8 bis 9 als die nächste rechte Rekursion.
funktion quicksort(links, rechts)
s := links - 1
pivot := daten[links + Int[[rechts - links + 1] / 2]]
// Nach Elementen kleiner als Pivot suchen
schleife "x" von links bis rechts
falls daten[x] < pivot dann
s := s + 1
tausche daten[s] mit daten[x]
ende
ende
// Nach Elementen identisch mit Pivot suchen
b := s + 1
schleife "x" von s + 1 bis rechts
falls daten[x] = pivot dann
tausche daten[b] mit daten[x]
b := b + 1
ende
ende
// Wenn zutreffend, die Rekursion "kleiner als..." starten
falls links < s dann
starte funktion quicksort(links, s)
ende
// Wenn zutreffend, die Rekursion "größer als..." starten
falls b < rechts dann
starte funktion quicksort(b, rechts)
ende
ende
--31.17.34.192 16:14, 18. Apr. 2022 (CEST)
schnelles Quicksort
Ich habe die beiden von mir entwickelten Pseudocodes (siehe oben) zu einem neuen vereint. Der Anfang und das Ende laufen auch hier wie beim ersten Code aufeinander zu, heißen aber nicht "i" und "j", sondern wie im zweiten Code "s" (smaller) und "b" (bigger). Ebenfalls wie beim zweiten Code, finden sich nach der Teilung alle Elemente die mit Pivot identisch sind, im Trennungsbereich zwischen "s" und "b". Hier befindet sich "s" aber immer eine Position weiter rechts und "b" immer eine Position weiter links. Wenn die Elemente "s" (smaller) und "b" (bigger) nicht getauscht werden können, dann läuft die "X-Suche" zwischen "s" und "b" so lange weiter, bis sie ein Element gefunden hat, das kleiner oder größer als Pivot ist und tauscht es mit der Position von "s" bzw. "b". Anschließend springt der Ablauf zurück zu den Positionen, wo kleinere bzw. größere Elemente als Pivot übersprungen werden.
Um eine unsinnige Code-Struktur zu vermeiden, die die Arbeitsgeschwindigkeit unnötig ausbremsen würde, war es zwingend erforderlich zwei Sprungzeilen und fünf Mal den Goto-Befehl zu verwenden.
funktion quicksort(links, rechts)
// Autor: Martin Oppermann
s := links
b := rechts
pivot := daten[s + Int[[b - s + 1] / 2]]
x := s
// Am Anfang kleinere Elemente als Pivot überspringen
kleiner: // Sprungzeile "kleiner"
falls daten[s] < pivot dann
s := s + 1
GoTo kleiner // Springe direkt zur Position Sprungzeile "kleiner"
ende
// Am Ende größere Elemente als Pivot überspringen
groesser: // Sprungzeile "groesser"
falls daten[b] > pivot dann
b := b - 1
GoTo groesser // Springe direkt zur Position Sprungzeile "groesser"
ende
// Wenn zutreffend, die Elemente "s" (kleiner) und "b" (größer) vertauschen
falls daten[s] > pivot und daten[b] < pivot dann
tausche daten[s] mit daten[b]
s := s + 1
b := b - 1
GoTo kleiner // Springe direkt zur Position Sprungzeile "kleiner"
ende
// Die Suchposition darf sich nicht vor dem Bereich "kleiner als..." befinden
falls x < s dann
x := s
ende
wiederhole solange x <= b // Do , 2 x If-Then , x := x + 1 , Loop Until x > b
// Nach kleineren Elementen als Pivot suchen
falls daten[x] < pivot dann
tausche daten[s] mit daten[x]
s := s + 1
GoTo kleiner // Springe direkt zur Position Sprungzeile "kleiner"
ende
// Nach größeren Elementen als Pivot suchen
falls daten[x] > pivot dann
tausche daten[x] mit daten[b]
b := b - 1
GoTo groesser // Springe direkt zur Position Sprungzeile "groesser"
ende
x := x + 1
ende
// Wenn zutreffend, die Rekursion "kleiner als..." starten
falls links < s - 1 dann
starte funktion quicksort(links, s - 1)
ende
// Wenn zutreffend, die Rekursion "größer als..." starten
falls b + 1 < rechts dann
starte funktion quicksort(b + 1, rechts)
ende
ende
--31.17.34.192 23:19, 18. Apr. 2022 (CEST)
