Diskussion:Quicksort

Kann bitte jemand mit Sysop-Rechten diesen Artikel nach QuickSort verschieben, damit wir innerhalb der Wikipedia eine einheitliche Schreibweise haben? --Head 11:08, 31. Aug 2003 (CEST)

was spricht - zumindest vorübergehend - gegen einen redirect? tsor 11:11, 31. Aug 2003 (CEST)

Ich finde eigentlich die Schreibweise mit großem S besser, weil leserlicher. Bei Quicksort ist das kein großes Problem, aber bei Pigeonholesort, Smoothsort und Binarytreesort schon eher. Natürlich sollte es dann auch einen Redirect von Quicksort nach QuickSort geben. Ich bin nur der Meinung, dass der Artikel QuickSort heißen sollte, wenn in ihm auch die Schreibweise QuickSort benutzt wird.

Ah, jetzt verstehe ich das erst. Derzeit ist QuickSort redirected nach Quicksort. Und Du willst das umdrehen. Das halte ich auch für sinnvoll, aber da brauchen wir tatsächlich einen admin. Bewirb Dich doch einfach als admin;-) tsor 11:47, 31. Aug 2003 (CEST)

Sowohl »QuickSort« als auch »Quick Sort« widersprechen vollkommen den Rechtschreibregeln der deutschen Sprache. Wenn es nach den Regeln geht, muß es entweder »Quicksort« oder »Quick-Sort« heißen (wobei mir ersteres als weit lesbarer erscheint, und wenn nur aus dem Grunde, daß es sich an Konventionen hält und nicht völlig meiner deutschen Sprachintuition widerspricht). --Mulk 15:20, 24. Jul 2006 (CEST)

Währe eine mathematische Fassung des Pseudocodes nicht leserlicher?

 Quicksort(S):
 1 if |S| < 2:
 2 return S
 3 wähle Pivot-Element y aus S
 4 S1 := Menge mit allen Elementen aus S, die kleiner als y sind
 5 S2 := Menge mit allen Elementen aus S, die größer oder gleich y sind
 6 return Quicksort(S1) + Quicksort(S2)

Meiner Meinung nach ist die mathematische Fassung deutlich lesbarer und besser nachvollziehbar. Was spräche dagegen, die mathematische zusärtlich zu der deskriptive Beschreibung in den Artikel aufzunehmen?

Was mich sehr gewundert hat, war, dass das Pivot Element im Artikel immer am rechten aeusseren Rand des Arrays war. Ich dachte bislang, die gaengige Implementierung des Quicksort wuerde das Median of Three Verfahren benutzen und bei Pivot-Element-nach-rechts handele es sich nur um eine Variante? --Mike@experimentelles.org 11:08, 26. Jul 2006 (CEST)

Meines Erachtens ist der Abschnitt unverständlich bis falsch: was passiert, wenn in der unteren Liste ein Element ist daß nach oben gehört, aber in der oberen Liste kein Element, was nach unten gehört ? Nach meinem Verständniss das Textes würde NICHTS passieren, und die untere Liste wäre faherhaft.

Ich bitte um Meinungen, ansonsten ädere ich den Text. --Alphager 22:22, 31. Mai 2005 (CEST) Beantworten

Nein, das verstehst du falsch. Die Grenze zwischen der oberen und unteren Liste wird ja erst im Verlauf und je nach Ausgang der Vergleiche festgelegt. Das ist nicht sehr leicht vorstellbar, aber es gibt Simulationen, z. B. [hier].

Meiner Meinung nach ist also das Prinzip richtig erklärt, aber das Beispiel ist falsch: In der fünften Beispielzeile müsste der Wert 9 mit dem ersten von rechts gefundenen Wert vertauscht werden, der kleiner ist als das Pivotelement 5, also mit der 2. Wenn niemand widerspricht, werde ich das demnächst mal korrigieren.Udm 16:21, 15. Jun 2005 (CEST)

Das Beispiel bezieht sich auf die Implementierung im Abschnitt drüber und ist somit richtig. --WhileTrue 23:15, 15. Jun 2005 (CEST)

Wenn man diesen Artikel ausdrucken möchte, werden die Farben der Tabellenzellen in "Variante 1" nicht ausgedruckt. Dieses passiert mit jeder Firefox-Version auf meinem Rechner. Könnte man evtl. hart-codierte Farben verwenden? --D135-1r43 14:33, 31. Jul 2005 (CEST)

Das Bsp. Variante 1 ist doch falsch oder???

Da das dritte Element kleiner gleich ist, wird dieses mit dem Indexelement vertauscht und der Index wandert zum dritten Element.

9 ist nicht kleiner als 5 ?????

Es gibt Verfahren für QuickSort die schaffen auch im Worst Case O(n log n). Allerdings beruhen die auf - nicht gerade einfachen - Verfahren zur Berechnung des Medians in O(n). Damit ist meines Erachtens die Aussage "Vollständig verhindern kann man das Eintreten des Worst Cases jedoch nicht." falsch. In der Praxis hab ich das Verfahren jedoch bis jetzt noch nie gesehen, sondern im akademischen Bereich. Dennoch einarbeiten? Limdul 14:48, 8. Jan 2006 (CET)

Median in O(n) bestimmen braucht meiner Meinung nach kein kompliziertes Verfahren. Einfach die n Elemente durchgehen und gucken was in der Mitte steht... Im Mittel braucht man für die Bestimmung des Median O(log n). -- MlaWU 20:32, 8. Jan 2006 (CET)

Schön wärs ;) Das Verfahren findet sich hier: http://web.informatik.uni-bonn.de/I/Lehre/Vorlesungen/InfoIV-SS04/Baier-InfoIV-SS04.pdf ab Seite 49, die Schlussfolgerung für QuickSort dann auf Seite 54 Limdul 01:02, 9. Jan 2006 (CET)

Genau das meinte ich. Das fällt noch nicht unter kompliziert, auch wenn es für die Praxis zu langsam ist :-) -- MlaWU 16:23, 9. Jan 2006 (CET)

Vor ein paar Jahren gab es in der c't einen Artikel. Der Titel hieß entweder "QuickerSort" oder er enthielt zumindest diesen Begriff. Der Clou in diesem Artikel war, Quicksort mit Bubblesort zu kombinieren, da beide Algorithmen unter unterschiedlichen Voraussetzungen degenerieren, sich also deshalb gegenseitig den Worst-Case vom Hals halten. Dabei wird im Prinzip der Quicksort-Algorithmus verwendet. Beim Scannen einer Teil-Liste, werden aber auch benachbarte Werte miteinander verglichen. Werden dabei Werte gefunden, die in der falschen Reihenfolge sortiert sind, dann werden auch diese getauscht (Bubblesort), Werden dagegen keine Unregelmäßigkeiten gefunden, dann ist klar, dass zumindest diese Teilliste bereits sortiert ist, und es findet keine Rekursion innerhalb dieser Teilliste mehr statt. Bei Listen, die bereits sortiert vorliegen, bricht der Algorithmus ohne Rekursion ab, ist also erheblich schneller, als QuickSort. Bei unsortierten Listen ist der Algorithmus geringfügig langsamer, als Quicksort. Auch unter ungünstigen Umständen, nimmt die Geschwindigkeit aber nicht so stark ab, wie bei Quicksort. Mein erkauft sich also eine wesentlich größere Robustheit mit einem geringfügigen Performance-Verlust

Ich kann hier nicht allzuviel zur Theorie beisteuern, denke aber, dass dies eine interessante Erweiterung des Artikels darstellt. Kann jemand etwas daraus machen?

Gruß, Matthias

Sowohl der Pseudocode für die abgewandelte Version der Funktion teile, als auch die Implementationen in Delphi, Visual BASIC und C enthalten alle denselben Fehler: Bei der Suche nach links und rechts nach einem Element, das größer bzw. kleiner als das Pivot-Element ist, wird nicht geprüft, ob die zulässigen Array Grenzen eingehalten werden. Das ist kein theoretischer Fehler, sondern der Code führt tatsächlich bei entsprechenden Eingangsdaten zu ungültigen Speicherzugriffen.

Konkret am C Code aufgezeigt:

	 while (a[li] < test)
	 li++;
	 while (a[re]> test)
	 re--;

Wie leicht zu sehen ist, crasht der Code sobald re < 0 bzw. li>= Arraygröße. Ob es dazu kommt, hängt davon ab, ob die while Schleife vorher abbricht, weil ein passendes Element gefunden wurde, oder nicht. Mit anderen Worten: Von den Eingangsdaten.

Interessanterweise findet sich dieser Fehler in> 50% aller Beispielimplementationen, die man im Web findet. Die Vermutung liegt nahe, dass da einer vom anderen abgeschrieben hat. Der Plagiarismus läßt grüßen:-)

Abhilfe: Die performanteste Lösung, die aber nur in wenigen Fällen möglich sein dürfte, ist das Einfügen eines Sentinel Elements an beiden Enden. Die nächstbeste Lösung ist eine zusätzliche Abbruchbedingung für die beiden Schleifen, die aber - weil es die inneren Schleifen sind - direkt auf die Laufzeit durchschlägt.

Gruss, Uz

In dem angegebenen Python code werden in jedem Rekursionsschritt neue Listen für die beiden Teile angelegt. Damit steigt der Speicherbedarf des Algorithmus ins Unermessliche. Gerade das ist aber nicht der Sinn von Quicksort. Eine bessere Implementierung für Python findet sich unter http://www.hib-wien.at/leute/wurban/informatik/sortieren/sort5_quick.pdf

(nicht signierter Beitrag von 87.193.42.221 (Diskussion) RolandH 22:33, 19. Jun 2006 (CEST))

Also, "unermesslich" ist der Speicherbedarf eigentlich nicht, er verhält sich (im worst case) quadratisch zur Problemgröße. In den Beispielen zu Haskell, Perl, Ruby, ... wird ebenfalls nicht in place sortiert, und das sind die Beispiele, bei denen der eigentliche 'Clou' bei Quicksort am deutlichsten erkennbar ist. Die Ruby-Version dürfte außerdem schneller als eine entsprechende in place-Version sein (Vergleich beider Varianten). Und dann gibt es da noch einen Spruch: 'premature optimization is the root of all evil'. Soll heißen, optimierter Code ist nur dann sinnvoll, wenn man ihn auch wirklich braucht. (PS: Bitte Diskussionsbeiträge mit ~~~~ signieren). RolandH 22:23, 19. Jun 2006 (CEST)

Der Pseudocode der abgewandelten Teile-Funktion konnte bis gerade beispielsweise die Folge [2,2,3,2,2] nicht sortieren. Das Programm verfing sich in einer Endlosschleife im ersten Teile-Aufruf, weil i an daten[0] kein Element> daten[4] findet und j an daten[3] kein Element < daten[4] findet bleiben beide unverändert. Weil sich aber die Zeiger nicht kreuzen wird die Schleife nicht abgebrochen und es passiert wieder das selbe.

Kann irgendwer die Sourcecodes auf diesen Fehler überprüfen? Ruby habe ich bereits korrigiert. Ich glaube, dass sich der Fehler auch im C Code findet.

Gruss, Andreas

Hi,

der Pseudocode ist nicht annähernd Ausreichend Kommentiert, so war bis eben (*ehem*) nichtmal erläutert was "Rechts und links" für Werte sind, geschweigedenn welche Funktion sie erfüllen.

Wurde hinzugefügt, aber eine ausführlichere Version wäre Wünschenswert...

mfg (nicht signierter Beitrag von 62.143.117.9 (Diskussion) chrislb 问题 15:27, 13. Mai 2006 (CEST))Beantworten

Anmerkung eines kritischen Lesers zur teile-Funktion: „!!! ACHTUNG FUNKTIONIERT NICHT : index und zeiger sind immer gleich" (Benutzer:213.147.182.253 ) --chrislb 问题 12:42, 26. Mai 2006 (CEST) Beantworten

Die Liste mit Implementierungen in verschiedenen Sprachen ist schon ziemlich lang und tendiert naturgemäß dazu, noch länger zu werden. Implementierungen in je einer funktionalen (Haskell?) und prozeduralen/objektorientierten Sprache (Java? Python? Ruby?) sollten doch eigentlich das Wesentliche abdecken... Auslagern? Kürzen? --RolandH 01:28, 21. Jun 2006 (CEST)

Ich bin auch für eine mathematische Darstellung. Die ganz am Anfang der Diskussion ist sofort verständlich. Man solte es nur formaler hinschreiben:

A: { a1, a2, ..., an } Alphabet

S1, S2, S3: { a | a € A } Mengen über A (€ = Element von)

≥(×ばつA) -> {wahr, falsch}: Prädikat (Wahrheitsfunktion) über ×ばつA

+: Konkatenation von Symbolen

Not: - Negation

|S|: - Mächtigkeit von S

Ergebnis: Liste einelementiger Mengen über A, sortiert nach ≥

quicksort (S)
begin
 if |S| < 2 then return S
 wähle beliebiges Element y aus S
 S1 = { a | a € A, not ≥(a, y) }
 S2 = { a | a € A, ≥(a, y) }
 Return quicksort(S1) + quicksort(S2)
end

"Wähle beliebiges Elelement y" bedeutet hier "zufällig". Somit ist sichergestellt, daß in unendlicher Zeit der Algorithmus terminiert. Das ist für den Fall |S| = 2 von Bedeutung (Es gilt die lexikale Ordnung):

1. quicksort({a, b})
2. wähle a
3. S1 = {ε}
4. S2 = {a, b}
5. quicksort({ε}) + {quicksort({a, b})
... usw.

Zufällig in unendlicher Zeit bedeutet, daß in Schritt 2 irgendwann einmal b gewählt wird:

1. quicksort({a, b})
2. wähle b
3. S1 = {a}
4. S2 = {b}
5. quicksort({a}) + quicksort({b})

... was zur Termination führt.

Die »Implementierungen« in den höheren (Skript-)Sprachen implementieren nicht den Quicksort-Algorithmus, sondern bestenfalls dessen grundlegendes Prinzip in besonders ineffizienter Weise. Ich hab sie deshalb gelöscht.

Wenn man z.B. schon in Perl mit grep arbeitet, kann man gleich

sub qsort { sort @_ }

schreiben (ab Perl 5.8 noch zusätzlich use sort "_quicksort";), was tatsächlich den Quicksort-Algorithmus verwendet (aber natürlich keine Implementierung auf Anwendungsebene ist). --84.150.134.18 13:02, 29. Jul 2006 (CEST)

Und was ist bei den funktionalen Sprachen unecht? -- MlaWU

Die tun doch exakt dasselbe wie der Perl-Code. Insbesondere arbeiten sie nicht inplace und brauchen doppelt so viele Vergleiche. Funktionale Sprache und Algorithmus ist ohnehin ein Wiederspruch in sich. --84.150.134.18 19:08, 29. Jul 2006 (CEST)

Bei Perl hast Du argumentiert, daß es das qsort schon eingebaut gibt. Ist das bei den funktionalen Sprachen auch so? Und was hat das mit inplace und doppelt soviele Vergleiche zu tun? An der Komplexität ändert das nichts. Ich sehe da nichts unechtes. -- MlaWU 22:57, 29. Jul 2006 (CEST)

PS: Ich bin übrigens dafür diesen Abschnitt deutlich zusammenzustreichen. Es reicht völlig, wenn da eine Pascal-ähnliche, eine C-ähnliche, eine funktionale und (eventuell) eine logische Sprache steht. Dann sieht man das Prinzip. Der Rest ist ohne nur ein austauschen von Schlüsselwörtern. -- MlaWU 23:00, 29. Jul 2006 (CEST)