Diskussion:Quicksort/Archiv

Diese Seite ist ein Archiv abgeschlossener Diskussionen. Ihr Inhalt sollte daher nicht mehr verändert werden. Benutze bitte die aktuelle Diskussionsseite, auch um eine archivierte Diskussion weiterzuführen.

Um einen Abschnitt dieser Seite zu verlinken, klicke im Inhaltsverzeichnis auf den Abschnitt und kopiere dann Seitenname und Abschnittsüberschrift aus der Adresszeile deines Browsers, beispielsweise

[[Diskussion:Quicksort/Archiv#Thema 1]]

oder als Weblink zur Verlinkung außerhalb der Wikipedia

https://de.wikipedia.org/wiki/Diskussion:Quicksort/Archiv#Thema_1

Lemmafrage

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)

Pseudocode

Währe eine matematische Fasung des Pseudocodes nicht lserlicher?

 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?

Mengen im mathematischen Sinn haben aber keine Reihenfolge und lassen keine Duplikate zu. --BODHISATTVA 10:50, 13. Jan. 2007 (CET)

Wahl des Pivot Elementes

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)

Unabhängig vom Auswahlverfahren für das Pivot-Element wird dieses doch immer (vorübergehend) an den Rand (üblicherweise rechts) verschoben... --BODHISATTVA 10:57, 13. Jan. 2007 (CET)

Prinzip:Unverständlich bis falsch

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)

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)

Farbcodierung

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)

Beispiel falsch?

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 ?????

Das Beispiel ist schon korrekt, nur wird eben der Zustand nach der Verschiebung gezeigt, das "dritte Element" ist also die 3, die mit 9 vertauscht wurde. --BODHISATTVA 11:08, 13. Jan. 2007 (CET)

QuickSort in O(n log n)

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)

QuickerSort

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

- Ich denke, das ist durch den Absatz Varianten und dem weiterführenden Artikel Introsort abgedeckt. --Nalpak01 22:12, 25. Okt. 2006 (CEST)

Fehler im Code/Algorithmus

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:-)

war zb. in Sedgewick, Algorithms in C++, Ausgabe von 1992 falsch, der aktuelle Code hat den zusätzlichen Test

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

Der Fall, dass re<0 ist oder li>=Arraygrösse ist wird aber nie eintreten, da li beginnend bei bspw. 0 inkrementiert wird und re bei Arraygrösse-2 (wennn Pivot in array[Arraygrösse-1) beginnend dekrementiert wird und die Aufgabe erledigt ist, sobald sich die beiden Indizes kreuzen. Selbst wenn nie ein passendes Element gefunden wird sind wir durch, sobald re li(=Arraygrösse-2) erreicht hat.--BODHISATTVA 11:45, 13. Jan. 2007 (CET)

Dass das nicht so ist, sieht man an obigem Code (den ich damals aus dem Artikel kopiert habe), dort wird beim Erhöhen nirgends geprüft, ob sich die Indizes kreuzen. Ist aber auch egal, weil der Code nicht mehr im Artikel steht und der Pseudocode inzwischen die Grenzen korrekt prüft - irgendjemand hat's korrigiert:-) Gruss, Uz

Das dürfte auch mit der Wahl des Pivotelements zusammenhängen, mit Pivotelement = oberstes (re) führt das Feld [ 2, 1, 0, .... ] beim Sortieren der ersten 3 Elemente zu einem ungültigen Index

Python Code ist fragwürdig

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) )

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)

Pseudocode nciht ausreichend erläutert...

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) )

Überarbeiten

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)

Das stimmt meiner Ansicht nach nicht. Während der Iteration über die Elemente wird zeiger immer inkrementiert, index aber nur dann wenn das Element kleiner gleich dem Pivot ist. Ich erlaube mir die "Überarbeiten"-Markierung zu löschen. --BODHISATTVA 13:15, 13. Jan. 2007 (CET)

etwas zu viele Sprachen

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)

Hab mal mit der groben Kelle gelöscht :) Der Code in Java/C sollte wirklich ausreichen, um das Prinzip zu verdeutlichen - da braucht niemand mehr ernsthaft analoge Beispiele in Delphi, VB und PHP, die sich nur in Feinheiten der Syntax unterscheiden. Sinnvoller erschien mir da, den Code aus dem Beitrag über Haskell hierher zu kopieren. --Cvk 17:48, 13. Sep 2006 (CEST)

Habe den gesamten Abschnitt gelöscht. Pseudocode ist zur Erklärung völlig ausreichend, und wenn nicht, dann halt den Pseudocode verbessern. Konkrete Codebeispiele gehören in ein Wikibook. --Revvar (D RT) 14:35, 20. Nov. 2006 (CET)

Hmmm ... zumindest das Haskell-Beispiel finde ich interessant ... aber evtl. sollte man so eine funktionale Implementierug irgendwie anders unterbringen ... --Jkrieger 22:39, 20. Nov. 2006 (CET)

Schwerverständlicher Pseudocode

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×A) -> {wahr, falsch}: Prädikat (Wahrheitsfunktion) über A×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.

Ich finde diese Version nicht unbedingt lesbarer als der Pseudocode, und auch etwas verwirrend (Was passiert mit Duplikaten, wenn wir S1, S2 etc. als Mengen definieren?). Zudem ist es sinnvoll, das Pivot nicht S1 oder S2 zuzuordnen, sondern einfach "in die Mitte zu setzen", eine normale Implementation würde hier einfach die obere und untere Grenze im Array an den nächsten rekursiven Aufruf übergeben. --BODHISATTVA 13:55, 13. Jan. 2007 (CET)

Unechte »Implementierungen«

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)

Das eingebaute sort von Perl war kein Argument, sondern sollte die Vorgehensweise in den hochsprachlichen Codefragmenten, nicht den Algorithmus zu implementieren, sondern möglichst »elegant« zur Lösung zu gelangen, ad Absurdum führen.

An der Komplexität ändert es auch nichts, wenn ich in den Rekursionen abwechselnd auf- und absteigend sortier. Trotzdem würd ich nicht versuchen, das als »Quicksort« zu verkaufen. Speziell inplace oder nicht kann auch durchaus was an der Komplexität verändern: Wenn dadurch nicht mehr die Vergleiche dominant sind, kann sie völlig anders ausschaun. Und wenn sich auch viele Theoretiker nicht für einen Faktor 2 (oder auch 1 Million) bei der Laufzeit intressieren, macht es doch einen gewissen Unterschied. --84.150.172.246 05:54, 30. Jul 2006 (CEST)

Bei Quicksort ist, falls nicht inplace, aber durch die Art der Rekursion bestimmt wieviel zusätzlicher Speicher benötigt wird. Und ob man in ein Feld im gleichen Array oder in einem anderen Array kopiert bleibt sich gleich. Den benötigten Speicher kann man zur Not auch vorher am Stück reservieren. Mehr als ein konstanter Faktor kommt dabei insgesamt nicht raus. Ändert also nix an der Komplexität. Worauf ich hinaus will: Es ist sicher nicht sinnvoll das in Perl so zu implementieren. In einer rein funktionalen oder logischen Sprache dürfte es aber schwierig sein, es anders zu machen. Dort ist das also mMn durchaus legitim. -- MlaWU 13:31, 30. Jul 2006 (CEST)

Für die Rekursion braucht man – unabhängig ob inplace oder nicht – immer Platz für maximal ungefähr 2 log₂ n Integer (als Schleife ausprogrammierte Rekursion und Abarbeitung des größeren Teils zuerst vorausgesetzt). Inplace braucht man dann noch konstanten Platz, um das Pivotelement zwischenzuspeichern (einfaches Pivotelement vorausgesetzt), während sonst halt Platz für ein komplettes zweites Feld benötigt wird. Dass (wie in den Codebeispielen) auch noch jede Rekursionsstufe eine eigene Kopie des jeweiligen Teilfelds hält, ist nicht zwingend. Wenn man den größeren Teil zuerst abarbeitet (was bei rein funktionalen Sprachen aber nicht steuerbar ist), entspricht das insgesamt auch nur höchstens einem dritten Feld, unabhängig von n. Umgekehrt heißt das allerdings, dass bei funktionaler Programmierung mit der Grep-Methode im Worst Case Speicher für n²/2 Elemente (plus dessen Verwaltung) nötig ist und in der Folge natürlich auch entsprechende Kopieraktionen.

Kopieren muss man inplace nicht jedes Element, sondern nur die, die im falschen Teilfeld sind. Bei nicht optimaler Wahl des Pivotelements ist das deutlich weniger als die Hälfte. In der Praxis kommt noch dazu, dass das Cacheverhalten besser ist, wenn insgesamt weniger Speicher im Spiel ist (umgekehrt hat hier allerdings der streng sequenzielle Zugriff der Grep-Methode auch seine Vorteile).

Ob es in der Praxis sinnvoll oder legitim ist, das grundsätzliche Problem anders zu lösen, ist zweitrangig. Mein Punkt ist der, dass es dann kein Quicksort in dem Sinn, wie es im Artikel derzeit beschrieben wird, mehr ist. Wenn man unter »Quicksort« nur noch das ganz grundlegende Prinzip (erster Satz von Quicksort#Prinzip) versteht, muss der ganze Artikel entsprechend angepasst werden. Von mir aus kann man die Haskell-Implementation mit dem zugehörigen Kommentar (oder besser einem ausführlicheren) wiederherstellen. Sie sollte aber erst am Schluss stehn. Die Skriptsprachen, wo eine praktische Anwendung völlig sinnlos ist, sollten aber entweder den eigentlichen Quicksort-Algorithmus illustrieren oder ganz rausgelassen werden. --84.150.193.13 19:51, 30. Jul 2006 (CEST)

Nun, es ging nur um die zeitliche Komplexität. Und die ändert sich in diesen Fall nicht. Es ist nur etwas mehr Speicher nötig, falls der Algorithmus nicht inplace arbeitet. Aber das ist eigentlich auch egal. Überarbeiten sollte man den Artikel sicher mal. Mir erscheint z.B. der erste Satz des Abschnittes "Laufzeit" doch sehr fragwürdig. Mal eine andere Frage: Warum hast Du eigentlich die TcL-Implementierung nicht rausgeworfen? Übersehen? -- MlaWU 20:53, 30. Jul 2006 (CEST)

Es ist mir nicht nur um die zeitliche Komplexität gegangen. Ob die zeitliche Komplexität überhaupt von der Komplexität der Vergleiche bestimmt wird, ist außerdem gar nicht von vornherein klar. Bei den in den Beispielen verwendeten einfachen Integervergleichen wird etwa in aller Regel der Aufwand für die Kopien und Kontrollstrukturen überwiegen, auch in der normalen Inplace-Implementation.

Das »meist« im (ehemaligen) ersten Satz von Quicksort#Laufzeit ist sicher nicht ganz korrekt. Die gelöschten Varianten verwenden z.B. fast alle das erste Element als Pivot. Ohnehin betrifft es nur Implementationen zu Demonstrationszwecken; jede ernsthafte Implementation, die nicht auf Daten mit genau bekannten Eigenschaften spezialisiert ist, verwendet mindestens das mittlere Element, eher aber ein zufälliges oder den Median aus 3 oder mehr (optimale Implementationen variieren die Methode mit der Feldgröße).

Der Tcl-Code teilt die Liste immerhin in einem einzigen Durchgang. Allerdings gilt das auch für den Ruby-Code. Wahrscheinlich hab ich ihn mir nicht genau genug angeschaut, weil er so lang wie die normalen Implementationen ist. Bei genauerer Betrachtung müsste er aber erst recht raus oder zumindest gut kommentiert werden, weil er zudem eine ternäre Variante implementiert. Überhaupt könnte man bei allen Implementationen kommentieren, welche Variante sie verwenden (insbesondere das zufällig gewählte Pivotelement im Java-Code). --84.150.193.13 22:33, 30. Jul 2006 (CEST)

PS: Das »etwas mehr Speicher« heißt bereits bei einem Feld mit 50'000 32-Bit-Werten, dass ein 32-Bit-Adressraum deutlich überschritten ist, wenn es bereits sortiert war (nötige Verwaltung gar nicht gerechnet). --84.150.193.13 05:37, 31. 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 ohnehin nur ein austauschen von Schlüsselwörtern. -- MlaWU 23:00, 29. Jul 2006 (CEST)

Aber hallo!? In funktionalen Sprachen implementierte Programme sind gleichermaßen algorithmisch, sie sind auch nicht "unechter" als z.B. eine entsprechende Version in Assembler, genausowenig wie eine rekursive Formulierung von Quicksort "unechter" ist als eine rein iterative, was auch immer "unecht" zu bedeuten hat (wahrscheinlich "nicht Fachinformatiker-Schreibtischtest-kompatibel", sorry). Der zugrundeliegende Algorithmus bleibt in allen Fällen der gleiche, er wird nur anders ausformuliert. Er ist auch in der funktionalen Variante vollständig beschrieben, insofern ist es nur pure Polemik und grundfalsch, das mit dem Rausschmeißen und Ersetzen der kompletten Implementierung durch eine intrinsische oder Standardbibliotheks-Funktion gleichzusetzen. Außerdem kann man in funktionalen Sprachen Quicksort auch so schreiben, dass keine doppelten Vergleiche bei der Partitionierung durchgeführt werden. Es bleibt also nur noch der Kritikpunkt, dass in funktionalen Sprachen Quicksort nicht in-place arbeitet. Oder andersrum formuliert: es bleibt also nur noch der Kritikpunkt, dass es seiteneffektfreie Implementierungen von Quicksort gibt (und noch dazu kürzer, klarer und weniger buganfällig - unerhört). Deshalb würde ich zumindestens die Haskell-Version und die Python- oder Perl-Version (wg. Verbreitung) drinlassen. --RolandH 17:49, 30. Jul 2006 (CEST)

Rein funktionale Sprachen sind in dem Sinn nicht algorithmisch, dass sie keinerlei Kontrolle über die Reihenfolge der Abarbeitung oder Nebeneffekten wie Speicherbedarf erlauben, soweit das Endergebnis davon nicht beeinflusst wird. Algorithmen sind hier also keine »genau definierte Handlungsvorschrift« [erster Satz von Algorithmus], sondern zu einem guten Teil nur Ansammlungen von Randbedingungen, die ein bestimmtes Ergebnis determinieren, ohne den Ablauf im Detail festzulegen (wobei es im Allgemeinen natürlich sowohl Vor- als auch Nachteile hat, die Optimierung zu einem größeren Teil dem Compiler zu überlassen).

Die einzige »Nebenwirkung« des normalen Quicksort-Algorithmus als Ganzem ist, dass das unsortierte Feld danach nicht mehr existiert, sondern sortiert ist. Häufig ist das exakt das gewünschte Ergebnis. Wie gesagt ist aber mein Kritikpunkt nicht, dass es auch eine rein funktionale Umsetzung des Quicksort-Prinzips gibt, sondern dass der Artikel im momentanen Zustand nicht das grundlegende Prinzip, sondern dessen übliche konkrete Umsetzung beschreibt. Wenn man sich auf das Prinzip beschränkt, bleibt nicht viel mehr als teile und herrsche (Informatik), und der Rest müsste als eine konkrete Ausgestaltung unter vielen möglichen gekennzeichnet oder in einen separaten Artikel ausgelagert werden. --84.150.193.13 19:51, 30. Jul 2006 (CEST)

I beg to differ. Auch in einer rein funktionalen Sprache gegossene Algorithmen sind "eine genau definierte Handlungsvorschrift" (bzw. ein Verfahren mit einer präzisen endlichen Beschreibung unter Verwendung effektiver Verarbeitungsschritte (Broy: Informatik), von einem zwingenden Vorhandensein einer zeitlich-sequentiellen (imperativen) Vorgabe der Abfolge solcher Verarbeitungsschritte steht da kein Wort. D. h. ein Algorithmus in Haskell verdient immer noch die Bezeichnung Algorithmus (und nicht nur "bestenfalls eine Implementierung des grundlegendes Prinzip von" whatever). Ich verstehe die restlichen Einwände (unterschiedliche Komplexität bei Laufzeit und Speicherplatz der verschiedenen Quicksort-Varianten), aber nicht, warum die funktionale Varianten letztlich nicht in den Artikel gehören sollen. Die sind ebenso Quicksort wie die imperativen Varianten. --RolandH 23:59, 30. Jul 2006 (CEST)

Meine ursprüngliche Aussage war natürlich zugespitzt und vielleicht auch etwas polemisch. Eine scharfe Grenze gibt es beim Kontrollverlust sicher nicht. Schon ein C-Programm ist im strikten Sinn keine »genau definierte Handlungsvorschrift« mehr. Aber Fragen wie die, ob ich bestimmen kann, dass das größere Teilfeld ohne Rekursion bzw. mit Endrekursion sortiert wird, entscheiden halt u.U. darüber, ob der Algorithmus einige KB oder einige GB (und entsprechend Zeit) benötigt. Das mag für den Theoretiker irrelevant sein; in der Praxis spielen solche Resourcenfragen aber durchaus eine Rolle.

Inzwischen ist der Artikel schon so, dass die funktionalen Varianten wesentlich besser reinpassen als zuvor. Ich werd wohl auch noch mal drübergehn, dann kann man sie (teilweise) wieder reintun. --84.150.193.13 05:37, 31. Jul 2006 (CEST)

Ich habe da jetzt mal ein bißchen rumeditiert. Da steckten doch einige Fehler drin. Z.B. hat da irgendwer effektiv und effizient vertauscht und so. Bleiben noch die Algorithmen. -- MlaWU 21:48, 30. Jul 2006 (CEST)

Verbesserung von teile

funktion teile(links, rechts)
    index := links
    von zeiger := links bis rechts-1
       falls daten[zeiger] < daten[rechts] // daten[rechts] ist Pivot
          tausche(index, zeiger)
          index := index + 1
    tausche(index, rechts) // Pivot an die Trennstelle setzen
    antworte index

Tausche nur Elemente, die kleiner als Pivot sind.

Dies funktioniert auch mit 1-2-1-2-3-2, ich habe es nachgerechnet. Außerdem habe ich ein Testprogramm geschrieben, das alle Feld-Belegungen bis zur Länge 8 systematisch durchprobiert (auch mit gleichen Elementen), um Sortieralgorithmen zu testen, und es funktioniert.

Übrigens sind die Namen der Indizes index und zeiger unglücklich; ein Zeiger ist was anderes als ein Index (zumindest in C / C++ unterscheidet man zwischen diesen). (nicht signierter Beitrag von Megatherium (Diskussion | Beiträge) ) (unterschreiben kannst du mit --~~~~, was dann automatisch durch deinen Benutzernamen + Datum + Uhrzeit erstetzt wird.)

Das Setzen des Pivotelements an die Trennstelle schlägt fehl, da index am Ende nicht auf der 3 sondern auf der ersten 2 verbleibt. Sollte ich mich irren, so wäre es trotzdem nicht der referenzierte Algorithmus (siehe WP:NOR).

Ja Zeiger und Index sind nicht ideal, aber Variablennamen wie k sind noch weniger für das Verständnis des Nichtinformatikers geeignet. Vieleicht sollte man Namen suchen die die inhaltliche Funktion besser wiederspiegeln. --Revvar (D Tools) 21:30, 30. Jun. 2007 (CEST)

Dass index am ende auf der 2 steht, macht gar nichts, dann wird eben 2 mit 2 getauscht. Wichtig ist nur, dass an der Trennstelle ein Element gleich dem Pivotelement steht, und dass links davon alle kleiner gleich und rechts alle größer gleich sind. Ob es so mit der Quelle übereinstimmt, weiß ich allerdings nicht.

Für die andere Version von teile ist eine ähnliche Verbesserung möglich:

 funktion teile(links, rechts)
   i := links-1
   j := rechts
   pivot := rechts
   fürimmer
     // Suche von links ein Element, das >= daten[pivot] ist
     i := i + 1
     solange daten[i] < daten[pivot]
        i := i + 1  
     // Suche von rechts ein Element, das < daten[pivot] ist
     j := j - 1
     solange (daten[j] >= daten[pivot]) und (j > links) // <- Änderung
        j := j - 1 
     // Abbruch, wenn sich i und j "kreuzen"
     falls i >= j
        abbruch
     // vertausche zwei unpassende Elemente
     tausche(i, j)
   endefürimmer
   // setze Pivot an die richtige Stelle und gib seine Position zurück
   tausche(i, pivot)
   antworte i 

Die j-Schleife hält nicht auf Elementen gleich Pivot, da diese nicht auf die andere Seite getauscht werden müssen. Auch das habe ich getestet. So stimmt der Code auch mit den Kommentaren überein, die schon vorhanden waren.

Zu NOR: bei Sachen wie Quicksort, die erstens recht einfach un zweitens schon Allgemeingut sind, finde ich es übertrieben, eine Version, die (vielleicht) nicht in genau dieser Form wissenschaftlich publiziert ist, als "eigene Forschung" zu bezeichnen. Man kann nicht zu allem eine Quelle in der wiss. Literatur angeben. Die zweite Version von teile ist ja auch nicht belegt; da heißt es nur: "Eine andere Version ist die folgende" (ups, hatte Signatur vergessen) --Megatherium 16:35, 1. Jul. 2007 (CEST)

Mit der 2 hast du recht, funktionieren tut es trotzdem. Je länger ich mich damit beschäftige deso mehr kommen mir Zweifel ob diese eine Variante überhaupt hier stehen sollte. Ich finde keine weiteren Referenzen auf diesen Algorithmus in der Fachliteratur, welche die Bedeutung, der expliziten Nennung, stützen würde. Das Laufzeitverhalten mit vielen gleichen Schlüsseln ist übrigens schlecht, da Schlüssel gleich dem Pivotelement allesamt in der linken oder bei deiner Variante eben in der rechten Teilliste landen. Die usprüngliche Implementierung ist da optimaler. Um mal Robert Sedgewick zu zitieren: „Es ist eine große Verlockung, Quicksort verbessern zu wollen ... Viele Ideen wurden ausprobiert ... doch meist führte das zu einer Enttäuschung.“. Ich werfe deshalb diese Implementierung und das zugehörige Beispiel raus, bis die Relevanz belegt wurde

"Man kann nicht zu allem eine Quelle in der wiss. Literatur angeben." - doch kann man, und gerade hier sollte es so sein.

Dein Verbesserungsvorschlag zum bereits optimierten Orginal führt imho zu einem schlechteren Laufzeitverhalten bei vielen Elementen mit gleichen Schlüsseln, welche über die Liste gleimäßig verteilt sind. Wurde diese Änderung bereits veröffentlicht und hat der wissenschaftlichen Prüfung standgehalten? Ich glaube kaum, und genau das ist was WP:NOR verhindern soll. So einfach ist eben auch Quicksort nicht. --Revvar (D Tools) 10:36, 2. Jul. 2007 (CEST)

Widerspruch in Abschnitt Laufzeit

"Für die Wahl des Pivotelementes sind in der Literatur verschiedene Ansätze beschrieben worden. Die Wahrscheinlichkeit des Eintreffens des Worst Case ist bei diesen unterschiedlich groß, aber immer ungleich Null."

und

"Durch die geschickte Wahl des Pivotelementes kann das mittlere schlechteste Verhalten verbessert werden. Das Eintreten des Worst Case kann sogar ausgeschlossen werden, wenn als Pivotelement stets der Median der zu sortierenden Folge gewählt wird."

widersprechen sich doch, oder irre ich mich? (Der vorstehende, nicht signierte Beitrag stammt von 217.230.149.237 (Diskussion • Beiträge) 15:10, 12. Jan. 2008 (CET))

Fehler im Struktogramm

In der Funktion "teile(daten, links, rechts)", Schleife "solange pivot <= daten[j] und j > links":

Die Anweisung muss "j:=j-1;" heißen! Der Pseudocode über dem Struktogramm ist richtig, doch der Schrifttyp macht es teilweise unmöglich die Variable als "j" zu erkennen. Es macht den Anschein, als ob es "i" hieße.(Der vorstehende, nicht signierte Beitrag stammt von 80.144.225.194 (Diskussion • Beiträge) 9:42, 13. Mär. 2008 (CEST))

Implementierungs-Sammlung

Hallo zusammen! Warum muss man in den Algorithmen-Artikeln immer anfangen tausend Implementierungen zu sammeln? Ich bin dafür das ganze auf den Pseudocode zu beschränken. Der ist ja schließlich allgemein für alle imperativen Programmiersprachen. Evtl. noch ein Beispiel in einer funktionalen Sprache (aber bitte gut lesbar!) Was mein Ihr? --Jkrieger 11:54, 2. Apr. 2008 (CEST)

Ich bin ebenfalls dagegen, dass Implementierungen in verschiedenen Programmiersprachen teil des Artikels sind. Das bläht den Artikel auf ohne neues über den Algorithmus zu berichten, um den es doch eigentlich geht. Evtl. könnte man ja für die Implementierungen eine eigenen Wiki-Eintrag vorsehen. Schmunzeldrache 10:20, 4. Apr. 2008 (CEST)

Fehler im Code/Algorithmus II

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 (nicht signierter Beitrag von 84.63.16.106 (Diskussion) ) Complex 21:45, 28. Apr. 2008 (CEST)

pseudocode

ich bitte nochmals darum dass der pseudocode wie in allen anderen artikeln auch auf englisch umgeschrieben wird, desweiteren bitte ich, dass mein eintrag nicht wieder gelöscht wird. wofür ist die diskussionsseite sonst da wenn nicht für vorschläge zum artikel (und leute die was dagegen haben?) (nicht signierter Beitrag von 84.60.243.142 (Diskussion) ) Complex 21:45, 28. Apr. 2008 (CEST)

Algorithmus im Strucktogramm ist falsch!

bei der Funktion "teile" steht im Strucktogramm: "solange pivot <= daten[j] und j < links, j:=j+1" dabei ergibt das keinen sinn, da j ja rechts anfängt und nach links wandert. Man muss das "j:=j+1" durch "j:=j-1" ersetzen! (nicht signierter Beitrag von 130.83.19.164 (Diskussion) )

Danke, ist korrigiert. --Noddy 12:10, 2. Mai 2008 (CEST)

Vorschlag zur Überarbeitung des Artikels

Der Quicksort-Artikel erscheint in mehrfacher Hinsicht überarbeitungsbedürftig. Die Gründe seien kurz erläutert:

Als Wichtigstes: Der durch den Pseudocode beschriebene Algorithmus ist nicht optimal. Der große Vorteil von Quicksort, über ausgesprochen kurze innere Schleifen zu verfügen wird verwässert. Einerseits enthalten die "wiederhole solange" - Schleifen zwei statt einer Bedingungsprüfung, andererseits werden vor dem Tausch der Elemente auf den Zeigerpositionen eben diese Positionen miteinander verglichen. Die Laufzeitnachteile halten sich mit ca. 10% in Grenzen, allerdings nur solange, wie die zu sortierende Folge nicht bereits geordnet ist und nur wenige Schlüsselwerte einander gleichen. Sobald eine dieser Voraussetzungen fehlt, wächst die Laufzeit dramatisch, es stellt sich (wie im Abschnitt Kenngrößen erwähnt) quadratische Zeitkomplexität ein. Hier bieten sich aus meiner Sicht drei Algorithmen an, die dem Leser des Artikels keine höheren Anforderungen bezüglich des Verständnisses abverlangen und die die benannten Nachteile weitgehend ausschließen. Diese Verfahren sollen weiter unten diskutiert werden.

Weiterhin enthält der Text eine Reihe kleiner Ungenauigkeiten. Folgende seien stellvertretend genannt: In der einführenden Erläuterung zum Pseudocode wird der Index des letzten Feldelements mit n bezeichnet, nachfolgend wird das letzte Feldelement mit [n-1] indiziert. (Möglicherweise wurde der Begriff Maximalindex unglücklich mit der Elementanzahl "in einen Topf geworfen"...). Die Beschreibung des Beispiels weicht vom Pseudocode ab, die Initialisierung der Zeiger i, j erfolgt an anderer Stelle, der Text spricht davon, dass die Zeiger bei einem Element >= bzw. <= dem Pivot stoppen, laut Pseudocode erfolgt der Stopp hingegen erst bei einem Element, das > bzw. < als das Pivotelement ist. Wie gesagt, die Aufzählung der Ungenauigkeiten lässt sich fortsetzen.

Schließlich scheint das zweite Beispiel für das Verständnis des Algorithmus nicht erforderlich. Und mal ehrlich - der durchschnittliche Leser des Quicksort-Artikels wird wohl kaum das Beispiel nachvollziehen, zumal Bezeichnerwahl und Algorithmus nicht mit dem Pseudocode übereinstimmen. Also, auch wenn viel Mühe im Text steckt, im Interesse unserer Leser sollten wir dieses Beispiel nicht in den überarbeiteten Text aufnehmen.

Der bisherige Algorithmus hat den didaktischen Vorteil, dass das Pivotelement sofort an die richtige Position getauscht wird. Die Nachteile hinsichtlich der Laufzeit sind allerdings beträchtlich. Sedgewick gibt einen etwas besserer Algorithmus mit eben dieser negativen Eigenschaften an, macht allerdings darauf aufmerksam, dass das Verfahren erst nach einer Verbesserung praxisgerecht einsetzbar ist und beschreibt ausführlich die Probleme und zugehörigen Verbesserungsmöglichkeiten. Die beiden ersten nun dargestellten Quicksort-Varianten wählen ein Pivot-Element aus der Mitte der jeweiligen Teilfolge, damit findet sich das Pivot am Schluss der Partitionierung leider nicht zwingend an der Teilungsstelle, die dritte Variante greift den von Sedgewick vorgeschlagenen Algorithmus mit Bestimmung des "Median von 3" auf. Der Quelltext ist in Pascal dargestellt, im Wikipedia-Artikel sollte hier natürlich eine Darstellung in Pseudocode stehen. Zudem werden nur Integers sortiert, im eigentlichen Artikel sollte man Bezug auf das Ordnen von Datensätzen nehmen.

 procedure QSort(Anfang,Ende:integer);
 var Links,Rechts,Vgl,H:integer;
 begin
   if Anfang<Ende then begin
     Links:=Anfang; Rechts:=Ende; Vgl:=Zahl[(Anfang+Ende) div 2];
     repeat
       while Zahl[Links]<Vgl do Inc(Links);
       while Zahl[Rechts]>Vgl do Dec(Rechts);
       if Links<=Rechts then begin
         H:=Zahl[Links]; Zahl[Links]:=Zahl[Rechts]; 
         Zahl[Rechts]:=H; Inc(Links); Dec(Rechts)
       end
     until Links>Rechts;
     QSort(Anfang,Rechts); QSort(Links,Ende)
   end
 end;

 procedure QSort(Anfang,Ende:integer);
 var Links,Rechts,Vgl,H:integer;
 begin
   if Anfang<Ende then begin
     Links:=Anfang-1; Rechts:=Ende+1; 
     Vgl:=Zahl[(Anfang+Ende+1) div 2];
     repeat
       repeat Inc(Links) until Zahl[Links]>=Vgl;
       repeat Dec(Rechts) until Zahl[Rechts]<=Vgl;
       H:=Zahl[Links]; Zahl[Links]:=Zahl[Rechts]; Zahl[Rechts]:=H
     until Links>=Rechts;
     Zahl[Rechts]:=Zahl[Links]; Zahl[Links]:=H;
     QSort(Anfang,Links-1); QSort(Links,Ende)
   end
 end;

 procedure QSort(Anfang,Ende:integer);
 var Links,Rechts,Vgl,Mitte,H:integer;
 begin
   if Anfang<Ende then begin
     Mitte:=(Anfang+Ende) div 2; Rechts:=Ende-1;
     if Zahl[Anfang]>Zahl[Ende] then begin
       H:=Zahl[Anfang]; Zahl[Anfang]:=Zahl[Ende]; Zahl[Ende]:=H
     end;
     if Zahl[Mitte]>Zahl[Ende] then begin
       H:=Zahl[Mitte]; Zahl[Mitte]:=Zahl[Ende]; Zahl[Ende]:=H
     end;
     if Zahl[Anfang]>Zahl[Mitte] then begin
       H:=Zahl[Anfang]; Zahl[Anfang]:=Zahl[Mitte]; Zahl[Mitte]:=H
     end;
     if Mitte=Rechts then Exit;
     Vgl:=Zahl[Mitte]; Zahl[Mitte]:=Zahl[Rechts]; 
     Zahl[Rechts]:=Vgl; Links:=Anfang;
     repeat
       repeat Inc(Links) until Zahl[Links]>=Vgl;
       repeat Dec(Rechts) until Zahl[Rechts]<=Vgl;
       H:=Zahl[Links]; Zahl[Links]:=Zahl[Rechts]; Zahl[Rechts]:=H
     until Links>=Rechts;
     Zahl[Rechts]:=Zahl[Links]; Zahl[Links]:=Zahl[Ende-1]; 
     Zahl[Ende-1]:=H;
     QSort(Anfang,Links-1); QSort(Links+1,Ende)
   end
 end;

In allen drei Verfahren lässt sich Worst-Case-ähnliches Verhalten im Prinzip nur durch besonders präparierte Dateien erzwingen. (Ein Angreifer, der den benutzten Algorithmus kennt, könnte mit einer speziell vorbereiteten Datei einen Server "in die Knie" zwingen.) Praktisch tritt dieser Fall (böser Wille ausgeschlossen) anders als beim bisher angegebenen Algorithmus nicht auf. Von der Laufzeit unterscheiden sich die Varianten nur unwesentlich mit geringen Vorteilen für das letzte Verfahren. Demzufolge kann man sich darauf konzentrieren, in welchem Fall das Prinzip von Quicksort am Besten verdeutlicht wird. Damit scheidet das letzte Verfahren aus, da die Bestimmung des Pivotelements hier zu stark in den Vordergrund rückt. Die Entscheidung zwischen erstem und zweiten Verfahren ist ein wenig Geschmackssache. Das erste Verfahren gefällt mir eigentlich besser, das zweite hat mehr Ähnlichkeit mit dem von Sedgewick als Basisverfahren gekennzeichneten.

Erwähnenswert erscheint noch folgende Quicksort-Variante, die in ähnlicher Form hier bereits diskutiert wurde.

 procedure QSort(Anfang,Ende:integer);
 var Z1,Z2,Vgl,H:integer;
 begin
   if Anfang<Ende then begin
     Z1:=Anfang; Vgl:=Zahl[Z1];
     for Z2:=Z1+1 to Ende do begin
       if Zahl[Z2]<Vgl then begin
         Inc(Z1); H:=Zahl[Z1]; Zahl[Z1]:=Zahl[Z2]; Zahl[Z2]:=H
       end
     end;
     H:=Zahl[Anfang]; Zahl[Anfang]:=Zahl[Z1]; Zahl[Z1]:=H;
     QSort(Anfang,Z1-1); QSort(Z1+1,Ende)
   end
 end;

Die Variante bringt auf Reihungen keine Geschwindigkeitsvorteile und zeigt für vorsortierte Folgen oder im Falle vieler gleichartiger Schlüsselwerte ein Worst-Case-ähnliches Verhalten. Allerdings lässt sich das Verfahren direkt auf das Sortieren einfach verketteter Listen übertragen., so dass es Eingang in einen Quicksort-Artikel finden sollte.

Bevor ich den Artikel verändere, hätte ich gern Rückmeldung von den Autoren, die bisher am Artikel gewirkt haben oder ebenso beabsichtigen, Veränderungen einzubauen. Man muss ja die Arbeit nicht mehrfach machen. Wenn also ohnehin jemand den Artikel überarbeitet, bitte ich meine Bemerkungen als Hinweis aufzufassen, wenn das nicht der Fall ist, bitte ich selbst um hilfreiche Hinweise.

--91.37.193.15 23:43, 19. Jun. 2008 (CEST)J.Adolf

Änderung zu Kenngrößen

Hier möchte ich die Änderungen am Abschnitt Kenngrößen kommentieren: Der Begriff "asymptotische Rechenzeit" wird ersetzt durch die besser geeignete "Zeitkomplexität". Die Aussage, dass im "Average Case" beide Teillisten gleichlang sind, ist falsch. Auch wenn sich im "Average Case" die gleiche Zeitkomplexität wie im Best Case ergibt, sind beide Fälle nicht identisch. Die Aussage, der "Worst Case" wäre vermeidbar, wenn der Median als Pivot gewählt wird, ist zumindest für die im Pseudocode beschriebene QuickSort-Variante falsch. Wenn alle Elemente gleichgroß sind, tritt genau der Worst Case ein. Diese Bemerkung wurde daher entfernt. Die Aussage, QuickSort wäre auf verketteten Listen nicht möglich, ist falsch. Daher ist diese Bemerkung entfernt. Unter Varianten ist hingegen eine Möglichkeit angegeben, wie sich QuickSort für einfach verkettete Listen implementieren lässt.

Weiterhin möchte ich den geneigten Leser auf folgendes hinweisen: Im Artikel wir eine recht unglückliche Variante von QuickSort benutzt. Je besser die Reihung bereits sortiert ist oder je mehr Schlüsselwerte einander gleich sind, desto mehr nähert sich die Zeitkomplexität dem Worst-Case-Verhalten, also O(n²). Außerdem wird der Vorteil der kurzen inneren Schleife z.T. aufgegeben (es geht kürzer). Für mich ist nicht erkennbar, warum gerade diese Variante gewählt wurde. Ein Blick auf anderssprachige Wikipedia-Eintäge zeigt nirgends diese Form. Falls jemand ein Argument für die Beibehaltung dieser Variante kennt, sollte er es angeben. Ansonsten würde ich eine andere Variante einstellen (siehe vorheriger Diskussionsbeitrag). Außerdem finde ich das vollständige Beispiel - bei aller Achtung ob der aufgewandten Mühe - fehl am Platze und möchte es entfernen (siehe vorheriger Diskussionsbeitrag). Auch hier möchte ich anregen, mir Gegenargumente zur Löschung des Beispiels zu benennen.

--91.37.196.170 23:13, 9. Aug. 2008 (CEST)J.Adolf

hat sich erledigt

Beispiel mit Farben und Zahlen wie bei den anderen *.Sort-Algorithmen

Jetzt ist es recht unverständlich für Laien... 141.24.172.38 14:13, 16. Jan. 2009 (CET)

Bildbeschreibung fehlt bei [[Bild:Wiki-quicksort.png]]

Der Artikel enthält ein Bild, dem eine Bildbeschreibung fehlt, überprüfe bitte, ob es sinnvoll ist, diese zu ergänzen. Gerade für blinde Benutzer ist diese Information sehr wichtig. Wenn du dich auskennst, dann statte bitte das Bild mit einer aussagekräftigen Bildbeschreibung aus. Suche dazu nach der Textstelle [[Bild:Wiki-quicksort.png]] und ergänze sie.

Wenn du eine fehlende Bildbeschreibung ergänzen willst, kannst du im Zuge der Bearbeitung folgende Punkte prüfen:

• Namensraum Datei: Bilder sollte im Namensraum Datei liegen. Bitte ändere die alten Bezeichnungen Bild: und Image: in Datei:.
• Skalierung: Außerhalb von Infoboxen sollten keine festen Bildbreiten (zum Beispiel 100px) verwendet werden. Für den Fließtext im Artikelnamensraum gibt es Thumbnails in Verbindung mit der automatischen Skalierung. Um ein Bild/eine Grafik in besonderen Fällen dennoch größer oder kleiner darzustellen, kann der „upright“-Parameter verwendet werden. Damit erfolgt eine prozentuale Skalierung, die sich an den Benutzereinstellungen orientiert. --SpBot 09:56, 2. Mär. 2009 (CET)

Struktogramm fehlerhaft

In der letzten Zeile des Quicksort-Struktogramms werden die Daten nicht übergeben. 217.7.147.90 11:13, 26. Mär. 2009 (CET)

Sortieren immer in O(n*log(n)) möglich.

Quicksort kann auch im ungünstigsten Fall in O(n*log(n)) sortieren, wenn man den Median korrekt bestimmt. Dieses ist in O(n) möglich.

--217.255.246.54 20:13, 27. Apr. 2009 (CEST).

Wie bestimmt man den Median in linearer Zeit? Mir fällt gerade nur „Quickselect” ein, mit einer worst-case-Laufzeit von O(n²). -- octo 13:29, 5. Jul. 2009 (CEST)

Eigenschaften von Quicksort (In-place)

Quicksort ist ein in-Place Algorithmus. Der entsprechende Passus ist nicht korrekt. vgl. http://www-is.informatik.uni-oldenburg.de/~dibo/hamster/band4/hamster4-html/node14.html

--85.176.35.13 11:21, 27. Aug. 2009 (CEST)

Vorschlag Beispiel

Ein Beispiel mit Zahlen ist i.d.R. einfacher Nachvollziehbar... (nicht signierter Beitrag von 139.18.199.20 (Diskussion | Beiträge) 13:51, 30. Aug. 2008 (CET))

Funktion teile(links, rechts) hat einen Fehler

• Probiert man den Alogrithmus mit der Zahlenfolge

   A = { A[1]=733, A[2]=727, A[3]=679, A[4]=697, A[5]=738, A[6]=712, A[7]=726, A[8]=707}

So tritt in der Funktion "Teile" bereits in der zweiten Iteration ein Fehler auf.

• Teile wird aufgerufen mit Teile(1,8). Das Pivotelement ist 707.
  • Die Schleife wird mit i=1 und j=8 gestartet und endet mit i=2 und j=7. Die Elemente A[1] und A[8] werden vertauscht.

   A = { A[1]=707, A[2]=727, A[3]=679, A[4]=697, A[5]=738, A[6]=712, A[7]=726, A[8]=733}

• • Jetzt wird die Schleife mit i=2 und j=7 gestartet, sie endet mit i=j=3 und A[2] und A[4] werden getauscht.

   A = { A[1]=707, A[2]=697, A[3]=679, A[4]=727, A[5]=738, A[6]=712, A[7]=726, A[8]=733}

• Die Schleife wird verlassen und i=3 wird zurückgeliefert. Damit entstehen die neuen Teilmengen {A[1], A[2]} und {A[3] .. A[8]}.

   A1 = { A[1]=707, {A[2]=697}
   A2 = { A[3]=679, A[4]=727, A[5]=738, A[6]=712, A[7]=726, A[8]=733}

Das ist der Fehler. A[3] hätte in A1 landen müssen, weil es kleiner als das Pivotelement 707 ist ! Ich würde den Algorithmus verwenden, der unter Quicksort-Uni-Flensburg zu finden ist. (nicht signierter Beitrag von Abkruger (Diskussion | Beiträge) 12:16, 3. Dez. 2007 (CET))

Ungenauigkeiten in der verbalen Beschreibung

Der Satz „Im Best Case (bester Fall) und Average Case wird das Pivotelement stets so gewählt, dass die entstehenden Teillisten beide gleich groß sind. In diesem Fall ist die Laufzeit des Algorithmus durch O(n•log(n)) nach oben beschränkt. Auch für den durchschnittlichen Fall gilt diese obere Schranke.“ birgt 2 Ungenauigkeiten in sich: 1) Wenn im AverageCase das Pivotelement wie im BestCase gewählt würde, wäre es kein AverageCase. 2) Die Bemerkung … ist nach oben beschränkt … suggeriert, dass bessere Zeitkomplexitäten möglich sind. Dies ist leider nicht der Fall. Daher folgender Formulierungsvorschlag: „Im Best Case (bester Fall) wird das Pivotelement stets so gewählt, dass die entstehenden Teillisten beide gleich groß sind. In diesem Fall gilt für die Laufzeit des Algorithmus O(n•log(n)). Auch für den Average Case (durchschnittlichen Fall) gilt diese Zeitkomplexität, auch wenn sich die Längen beider Teillisten im Durchschnitt z.B. wie 1:2 zueinander verhalten.“

Weiterhin sind 2-3-4-Bäume ein Sonderfall der B-Bäume, es wird aber der Eindruck erweckt, dies wären unterschiedliche Datenstrukturen. Schließlich funktioniert Quicksort auf doppelt verketteten Listen hervorragend, so dass der Link auf adaptiertes 2-Phasen-2-Band-Mischen wegen des Bezugs zu doppelt verketteten Listen unglücklich ist. Auch hier sollte man geschickter formulieren.

Ansonsten vielen Dank an den Autoren, der sich hier der öffentlichen "Bemeckerung" preisgegeben hat ... .

J.Adolf (nicht signierter Beitrag von 79.192.215.69 (Diskussion | Beiträge) 13:53, 6. Jun. 2008 (CET))

komplexitäten

Während für eine theoretische betrachtung die gesamtlaufzeit in landau notation ja ganz nett ist, spielt in der praxis der unsichtbare konstate faktor meist eine recht grosse rolle. In vielen Anwendungen besteht in der laufzeit ein recht grosser unterschied zwischen vergleich und vertauschung. Nehmen wir einmal in C eine reihe von strings: das vertauschen der pointer ist sehr schnell (2 mal xor) aber der vergleich kann bei längeren strings schonmal ne weile dauern.

Hier möchte man vermutlich gerne eine recht geringe menge an vergleichen und würde dafür einige vertauschungen mehr in kauf nehmen.

Ich denke es sollte hier eine genauere betrachtung geschehen, in wie weit man quicksort (oder auch introsort) in die eine oder andere richtung beeinflussen kann, nicht zuletzt indem man es als 3-way sort auslegt. Betrachtungen in landau symbolen von der anzahl der vergleiche und vertauschungen wären hier für die praxis wohl wesentlich besser.

Einmal als beispiel: vergleiche ich per GNU std::sort (ein introsort) 24000 zufällige zahlen, so komme ich (im aktuellen testfall) auf fast 420000 vergleiche, mit der microsoft qsort (auch ein introsort) variante sind es lediglich knapp 66000. Ist jetzt der vergleich wesentlich teurer als ein vetauschen bedeutet das in der gesamtlaufzeit ein geschwindigkeitsvorteil von 6 fach! (nicht signierter Beitrag von 217.11.197.10 (Diskussion | Beiträge) 12:35, 14. Sep. 2009 (CEST))

Pseudocode enthält Fehler

falsch:

...

        falls i ≤ j dann 
            tausche daten[i] mit daten[j]
            j := j - 1
            i := i + 1
        ende

    solange i ≤ j // solange i an j nicht vorbeigelaufen ist 

...

richtig:

...

        falls i < j dann 
            tausche daten[i] mit daten[j]
            j := j - 1
            i := i + 1
        ende

    solange i < j // solange i an j nicht vorbeigelaufen ist 

... (nicht signierter Beitrag von 77.74.2.65 (Diskussion | Beiträge) 16:26, 27. Aug. 2009 (CEST))

Ich versuche das gerade zu implementieren und so stimmt es leider auch nicht. Soweit ich das sehe muss hinter die Zeile

        // Tausche Pivotelement (daten[rechts]) mit neuer endgültiger Position (daten[i])

noch der Code

        falls daten[i] < pivot
            i := i + 1 

Dieser Fall tritt dann auf, wenn gegen Ende des Durchlaufes i und j genau gleich sind und auf ein Element zeigen, das in die linke Liste sollte. Dieses Element würde dann jedoch nach dem alten Code mit dem Pivot-Element vertauscht werden, also an das Ende der Liste gesetzt, was falsch ist. Wadi 18:35, 2. Jan. 2010 (CET)

Codebeispiele

So wie ich das beim Überfliegen sehe, sind die Beispielimplementierungen oft zwar dem Pseudocode ähnlich, aber kaum exakt gleich. Beispielsweise wird im Pseudocode als Pivotelementes immer das äußerst linke Element gewählt, der Javacode wählt stattdessen ein zufälliges Element, der Pascal-Code das Mittlere. Wäre es nicht sinnvoller, den Algorithmus stattdessen eins zu eins abzubilden und die Detailunterschiede zu entfernen? (nicht signierter Beitrag von 194.8.198.62 (Diskussion | Beiträge) 13:21, 16. Aug. 2006 (CEST))

Habs mal in einer Nacht- und Nebelaktion geändert. Finde den PHP-Code jetzt allerdings ziemlich überflüssig - sieht halt aus wie der C/Java-Code mit nem $ vor den Variablen... Löschen? --87.78.154.84 (nicht mit einer Zeitangabe versehener Beitrag von 87.78.154.84 (Diskussion | Beiträge) 02:44, 22. Aug. 2006 (CEST))

Habe den Verdacht, dass die divide()-fkt im beispiel nicht richtig funktioniert. (nicht signierter Beitrag von 153.96.32.62 (Diskussion | Beiträge) 14:18, 16. Feb. 2010 (CET))

Gif-Animation

Die erste Grafik im Artikel ist zwar vom der Konzeption her hervorragend, aber dennoch enzyklopädisch wertlos, da sie so schnell animiert ist, dass man den einzelnen Schritten als in die Materie nicht eingeweihter auch nach Artikellektüre nicht folgen kann. Ich plädiere für eine Drosselung des Tempos auf 10%. --Carbenium 18:47, 21. Apr. 2010 (CEST)

Fehler im Struktogramm von Funktion "quicksort"

ACHTUNG: Fehler im Struktogramm von Funktion "quicksort". Im Methodenaufruf fehlt der Parameter "daten". -- 141.31.15.96 (Aus dem Artikel hierher verschoben. --Krd 19:37, 31. Mai 2010 (CEST))

inplace

das quicksort nicht in-place arbeitet sollte wie bei den anderen sortierverfahren schon bei der zusammenfassung aufgeführt werden.

-- 92.195.27.167 22:30, 30. Sep. 2010 (CEST)

Formulierung

die Formulierungen größer dem Pivotelement und kleiner dem Pivotelement in den Sätzen nach dem Pseudocode sollten besser heissen größer als das Pivotelement bzw. kleiner als das Pivotelement. Nicht so arg schlimm, wäre aber besseres Deutsch. Ist weiter unten korrekt. --Embyro 21:24, 4. Okt. 2010 (CEST)

Fehler im Pseudocode

Nach genauerem Durchlesen des Pseudocodes ist mir aufgefallen, dass

 funktion quicksort(links, rechts)
     falls links < rechts dann
         teiler := teile(links, rechts)
         quicksort(links, teiler-1)
         quicksort(teiler+1, rechts)
     ende
 ende

wohl eher

 funktion quicksort(links, rechts)
     falls links < rechts dann
         teiler := teile(links, rechts)
         quicksort(links, teiler)
         quicksort(teiler+1, rechts)
     ende
 ende

heißen sollte, da ansonsten ein Element in der zu sortierenden Liste nicht mitsortiert wird. Hab das ganze im Artikel selber noch nicht abgeändert, da ich mir nicht zu 100 % sicher bin, falls jemand jedoch das selbe Problem sieht bitte sagen.

-- 188.174.49.79 21:45, 30. Jan. 2011 (CET)

Nööö, sollte OK so sein, da teile die Elemente in größer und kleiner teilt. Nach dem AUfruf von teile() gilt: Alle kleinere Elemente kleiner als teiler sind links von teiler und alle größeren (als teiler) sind rechts von teiler. Damit ist teiler schon richtig einsortiert, muss also in weiteren Schritten nicht mehr sortiert werden ... und die Version im Artikel ist korrekt. --Jkrieger 22:13, 30. Jan. 2011 (CET)

Laufzeit im worst-case = O( n log n) möglich!

Da sich der Median in O(n) berechnen lässt, kann Quicksort auch im worst-case in O(n log n) sortieren, wenn man den Median auf die entsprechende Weise bestimmt. (nicht signierter Beitrag von 79.203.110.115 (Diskussion) 02:58, 8. Feb. 2011 (CET))

Test-Programm für Quicksort

Ich habe in Basic ein Test-Programm für Quicksort geschrieben, das mir anzeigt, wie viele Klone (Rekursionen) Quicksort beim sortieren von sich selbst erstellt hat und wie viele davon maximal gleichzeitig parallel aktiv waren. Ich könnte auch Listen sortieren, die man mir mit einer Datei zukommen lässt. Kann ich damit etwas zum Artikel beitragen? Mein Programm verwendet den Pseudocode, den ich auf der folgenden Internetseite gefunden habe: http://www.bluffton.edu/~nesterd/java/SortingDemo.html --91.34.190.226 22:41, 19. Nov. 2011 (CET)

Ich habe mit meinen Programm bereits etwas entdeckt:

1.

Im "Worst-Case"-Fall ist die Anzahl der erstellten Rekursionen immer doppelt so hoch, wie die Anzahl der Werte im Array minus zwei. R=A*2-2

2.

Im "Worst-Case"-Fall ist die maximale Anzahl der gleichzeitig parallel aktiven Rekursionen, immer gleich der Anzahl der Werte im Array. R(max)=A

3.

Wenn zufällig erstellte Listen aus Zahlen sortiert werden, dann gibt es mit einer fortschreitenden Anzahl von Werten im Array (Liste) Bereiche, in denen - wie bei 2. - die maximale Anzahl der gleichzeitig parallel aktiven Rekursionen, immer gleich der Anzahl der Werte im Array ist. Diese Bereiche scheinen immer in Gruppen von mehreren Hundert Ereignissen zu kommen. Vermutlich existiert hier ein mathematisches Phänomen, das man nicht erklären kann. Bei Interesse könnte ich ja mal ein Diagramm berechnen lassen, auf dem man sich ansehen kann, wann diese Bereiche auftauchen. Vielleicht existiert ja eine Gesetzmäßigkeit. Im Diagramm würde dann nach rechts die Anzahl der Werte dargestellt. Die Anzahl der erzeugten Rekursionen und deren maximal gleichzeitig aktive Anzahl, würde dann in der Form von zwei Linien durch das Diagramm laufen.

--91.34.190.226 12:57, 20. Nov. 2011 (CET)

Pseudo-Code für Quicksort

Wenn man vorzeichenlose Datentypen als Index verwendet, kann es bei dieser Darstellung zu einem Überlauf kommen.

Bspw. für einen vorzeichenlosen 4 Byte Integer ergibt sich für 0 - 1 = 4294967290 anstatt - 1. (Bezogen auf die Programmzeile "quicksort(links, teiler-1)")

funktion quicksort(links, rechts)
    falls links < rechts dann
        teiler := teile(links, rechts)
        quicksort(links, teiler-1)
        quicksort(teiler+1, rechts)
    ende
ende

In diesem Fall wäre es besser, eine zusätzliche Abbruchbedingung hinzuzufügen:

funktion quicksort(links, rechts)
    falls links < rechts dann
        teiler := teile(links, rechts)
        falls teiler > 0 dann
            quicksort(links, teiler-1)
        quicksort(teiler+1, rechts)
    ende
ende

Die Verwendung von signed-Datentypen ist wegen der fehlenden Bedingung evtl. performanter, bei sehr großen Datenmengen kann die Verwendung von Unsigniert-Datentypen notwendig sein. Ich habe es mir zur Gewohnheit gemacht Unsigniert zu verwenden, wenn mir bewusst ist, dass der Bereich der natürlichen Zahlen ausreichend ist. Für Indizes ist das immer so. Insofern war dieser Teil ein kleiner Fallstrick für mich. Wäre ein Hinweis auf diese Problematik angebracht. Im Artikel ist ja ohnehin nur Pseudocode zu lesen, so das Eigenheiten von Programmiersprachen nicht berücksichtigt werden müssen. (nicht signierter Beitrag von 87.157.63.38 (Diskussion) 05:29, 11. Feb. 2012 (CET))

Pseudocode

Was soll das? Dieser Pseudocode ist ja echt unter aller Sau. Total unterste Schublade. Wenn man schon Pseudocode verwendet dann bitte auf Englisch, so wie es sich gehört, das ist ja nicht anzusehen. (nicht signierter Beitrag von 178.189.113.82 (Diskussion) 09:42, 7. Mai 2013 (CEST))

Wenn du Englisch besser verstehst als Deutsch, wie wäre es hiermit: en:Quicksort? --Plankton314 (Diskussion) 11:10, 7. Mai 2013 (CEST)

Der Pseudocode endet in einer Endlosschleife mit dem Array {31,5,26,41,9,15,1} --Jakry01 (Diskussion) 19:05, 11. Feb. 2014 (CET)

Ich fürchte, da hat sich Dein Programm irgendwo vertan. Dieses Array wird von diesem Pseudocode völlig korrekt sortiert. (Jedes andere Array übrigens auch.)

Der Code ist "wasserdicht". --Pyrometer (Diskussion) 12:54, 12. Feb. 2014 (CET)

Das Array {7,3,8,9,4,5,1,6,5,4,5} wird mit diesem Pseudocode nicht richtig sortiert. Die letzte if-Frage muss noch mit einem else ergänzt werden, um das richtige Pivot zurückzugeben, wenn das Pivot nicht getauscht werden kann.

 // Tausche Pivotelement (daten[rechts]) mit neuer endgültiger Position (daten[i])
   
 falls daten[i] > pivot dann
     tausche daten[i] mit daten[rechts]
 sonst
     i := rechts
 ende

(nicht signierter Beitrag von 212.117.101.66 (Diskussion) 18:37, 5. Jan. 2015 (CET))

Beim Array {2, 3, 1} gibt die Funktion teile beim ersten Durchlauf den Wert 0 zurück. Deshalb wird anschließend quicksort(0, 0-1) ausgeführt. Bei einer Implementierung mit vorzeichenlosen Variablen der Position führt das zum Überlauf und der Algorithmus schlägt fehlt. Man könnte entweder die if-Abfrage vor dem Aufruf von Quicksort durchführen oder sollte meiner Meinung nach zumindest darauf hinweisen. So sähe es umgeschrieben aus:

 funktion quicksort(links, rechts)
   teiler:= teile(links, rechts)
   falls links + 1 < teiler dann
     quicksort(links, teiler-1)
   ende
   falls teiler + 1 < rechts dann
     quicksort(teiler+1, rechts)
   ende
 ende

(nicht signierter Beitrag von 178.1.144.182 (Diskussion) 02:06, 28. Jun. 2015 (CEST))

in-place

Alle bisherigen Belege dafür, dass Quicksort 'in-place' implementierbar sei, die ich bisher gesehen habe, unterschlagen den Speicherverbrauch der Rekursion (z.B. Stack). Das widerspricht aber der Definition von in-place.

Die Behauptung, Quicksort könne in-place implementiert werden, habe ich daher erst einmal auskommentiert. Ich freue mich auf einen Beleg für in-place, der einer Überprüfung standhält.

--arilou (Diskussion) 17:49, 26. Nov. 2020 (CET)

Hallo Arilou,

du beziehst dich auf, Spezial:Diff/205960150. Was ist der Einwand: Weil für jede Rekursion (abhängig vom Pivot-Element) die Zeiger auf das rechte und linke Element notwendig sind. Andererseits sind diese Zeiger vernachlässigbar gegenüber den zu sortierenden Elementen und haben im Vergleich zur Eingabe nur die Platzkomplexität ${\mathcal {O}}(\log n)$. Solche Zeiger werden genau genommen bei jedem Programm benutzt. Deshalb wird in en:In-place algorithm nicht behauptet, dass in-place Algorithmen in ${\mathcal {O}}(1)$ arbeiten könnten. DAS GEHT EINFACH NICHT. Zumindest nicht wenn das Berechnungsmodell auch die Komplexität diverser Zeiger betrachtet.

Der Fehler ist also nicht hier zu suchen, sondern im Artikel In-Place-Algorithmus. In Zukunft solltest du besser recherchieren ehe du einen schlechten WP:Stub ohne Quellenangaben über den Weg traust. Ich mache jetzt deine Änderung rückgängig und ergänze einen Baustein im fraglichen Artikel.

Viele Grüße --Bejahend (Diskussion) 23:01, 1. Dez. 2020 (CET)

Hallo nochmal, ich habe mich gestern Abend etwas im Ton vergriffen und bitte um Entschuldigung. Tu was du für richtig hältst im rückseitigen Artikel, ich kümmere mich derweil um die Definition von in-place. VG --Bejahend (Diskussion) 08:38, 2. Dez. 2020 (CET)

Funktionaler Quicksort

Der Abschnitt "QuickSort in funktionalen Sprachen" behauptet das Quicksort sich in funktionalen Sprachen "aufgrund mächtigerer Listenverarbeitung sehr einfach implementieren" lässt. Dabei wird wohl unterschlagen, dass in reinen funktionalen Sprachen zustandslos gearbeitet wird. Ein wichtiger Punkt bei Quicksort ist jedoch dass der Algorithmus in-place auf einem Array arbeitet. Wie das mit einem Programm gehen soll, das auf Listen arbeitet und noch dazu in einer funktionalen Sprache geschrieben ist, ist mir schleierhaft. Ich bin daher der Meinung, man sollte aus dem Abschnitt entweder eine ernsthafte Diskussion machen oder ihn löschen, weil er eine falsche Behauptung aufstellt. --Svenhart (Diskussion) 19:10, 23. Dez. 2020 (CET)

Da es in rein funktionalen Sprachen auch so etwas wie Adressen nicht gibt weiß ich nicht wie sinnvoll es ist darüber zu Diskutieren ob etwas in-place ist. Die Formulierung "sehr einfach" finde ich hier nicht passend, für jemand der nicht programmieren kann ist der gegebene Code wohl gänzlich unverständlich. --BlauerBaum (Diskussion) 22:39, 26. Dez. 2020 (CET)

1. "Ein wichtiger Punkt bei Quicksort ist jedoch dass der Algorithmus in-place auf einem Array arbeitet." Das ist Ihre Meinung. Andere Leute finden womöglich andere Aspekte von Quicksort "wichtig".
2. In funktionalen Sprachen gibt es oft keine Arrays, sondern nur Listen.
3. Die Beschreibung "sehr einfach" sollte imo durch "sehr kurz" ersetzt werden; weder Haskell noch Erlang sind weitverbreitete Sprachen, und "einfach (zu verstehen)" sind wohl beide (für Programmierer anderer Sprachen) nicht ~ darin möchte ich meinen beiden Vor-Diskutierenden zustimmen.

--arilou (Diskussion) 18:45, 30. Dez. 2020 (CET)

Prinzipiell kann man das in-place Argument auch auf Listen anwenden, d.h. es wird dann eben keine zweite Liste bzw. keine kopierter Datensatz benötigt. Ansonsten würde ich auch der Formulierung sehr kurz statt sehr einfach zustimmen. Funktionale Sprachen erlauben oft sehr kurze eventuell auch als elegant zu bezeichnende Implementierungen, aber einfach im Sinne von leicht verständlich oder intuitiv lesbar sind sie eher nicht. Im Gegenteil für Leute die nicht regelmäßig mit funktionalen Sprachen arbeiten sind sie auf den ersten Blick eher unverständlich.--Kmhkmh (Diskussion) 23:07, 30. Dez. 2020 (CET)

Zu lange Beispiele

Die beiden Beispiele nehmen zu viel Platz auf der Seite weg. Man müsste sie komprimierter darstellen. --91.2.9.223 19:56, 10. Feb. 2013 (CET)

9 Jahre alt - weg.

Archivierung dieses Abschnittes wurde gewünscht von: --arilou (Diskussion) 09:33, 28. Jan. 2022 (CET)

Pseudocode

In dem Abschnitt des Pseudocodes, in dem links nach einem Element größer gleich dem Pivot Element gesucht wird, steht im Pseudocode als Bedingung "daten[i] <= pivot" (ich weiß nicht, wie man das "hübsch" hinschreibt, ich glaube ihr wisst aber alle, was ich meine). Genauso im Nächsten Code Block; auskommentiert wurde, dass rechts nach einem Element kleiner gleich dem Pivot Element gesucht wird, im Pseudocode steht aber "daten[i] >= pivot". Sieht für mich wie ein Fehler im Pseudocode aus und nicht nach einem Fehler in der Kommentierung.

Edit: Erster Beitrag, hab gedacht das hier wird irgendwie automatisch zu dem Pseudocode Segment hinzugefügt. Wäre nett, wenn das ein Admin oder so machen kann ;) Sorry nochmal (nicht signierter Beitrag von 95.115.126.86 (Diskussion) 17:32, 26. Sep. 2015 (CEST))

Ich kann keinen Fehler erkennen. Es wird nach einem Element gesucht, das größer ist als pivot, also steht in der Bedingung "solange ein Element kleiner oder gleich ist, ignoriere es und probiere es mit dem nächsten". Im nächsten Schritt umgekehrt aber entsprechend. Kommentar und Code stimmen also jeweils überein. --MRewald (Diskussion) 00:18, 28. Sep. 2015 (CEST)

Hat seit 7 Jahren niemanden gestört - kann weg.

Archivierung dieses Abschnittes wurde gewünscht von: --arilou (Diskussion) 09:35, 28. Jan. 2022 (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)

1. Begrenzungen bestimmter Programmiersprachen sind nicht relevant für die allgemeine Beschreibung eines Sortierverfahrens.
2. 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.
3. 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)

Archivierung dieses Abschnittes wurde gewünscht von: --77.22.10.106 14:05, 24. Feb. 2023 (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)

Archivierung dieses Abschnittes wurde gewünscht von: --77.22.10.106 14:07, 24. Feb. 2023 (CET)

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)

Archivierung dieses Abschnittes wurde gewünscht von: --77.22.10.106 14:07, 24. Feb. 2023 (CET)

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)

Archivierung dieses Abschnittes wurde gewünscht von: --77.22.10.106 14:07, 24. Feb. 2023 (CET)

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)

Archivierung dieses Abschnittes wurde gewünscht von: --77.22.10.106 14:07, 24. Feb. 2023 (CET)

Grundsätzliches Problem von Quicksort (Endlosschleifen durch identische Werte)

Mir ist aufgefallen dass praktisch alle Quell- / Pseudocodes von Quicksort, die man im Internet und teilweise auch in Fachliteratur finden kann, den gleichen fatalen Fehler haben: Sie geraten unweigerlich in eine Endlosschleife, wenn es mindestens zwei identische Werte im Array gibt. Dieser Fehler kann nur dadurch behoben werden, indem man die rechte Teilung (>= Pivot) immer dann noch einmal teilt, wenn sich "i" nach der ersten Teilung, immer noch auf der Position "L" befindet. Pivot behält hierfür seinen vorherigen Wert und nun wird alles was mit Pivot identisch ist links und alles was größer ist, rechts angeordnet. Anschließend braucht dann nur die rechte Seite als neue Rekursion gestartet zu werden.

Hier das entsprechende Codebeispiel des "abgesicherten Quicksort":

Sub Quicksort(L, R)
If R - L < 1 Then Exit Sub
i = L
j = R
p = Daten(L + Int((R - L) / 2))
Do
If Daten(i) < p Then i = i + 1
If Daten(j) >= p Then j = j - 1
If Daten(i) >= p And Daten(j) < p And i < j Then
	TEMP = Daten(i)
	Daten(i) = Daten(j)
	Daten(j) = TEMP
	i = i + 1
	j = j - 1
End If
Loop Until i > j
If L < i - 1 Then Call Quicksort(L, i - 1)
If j + 1 < R Then
	If L < i Then
		Call Quicksort(j + 1, R)
	Else
		j = R
		Do
		If Daten(i) = p Then i = i + 1
		If Daten(j) > p Then j = j - 1
		If Daten(i) > p And Daten(j) = p And i < j Then
			TEMP = Daten(i)
			Daten(i) = Daten(j)
			Daten(j) = TEMP
			i = i + 1
			j = j - 1
		End If
		Loop Until i > j
		If j + 1 < R Then Call Quicksort(j + 1, R)
	End If
End If
End Sub

--77.22.10.106 14:31, 29. Jan. 2023 (CET)

Archivierung dieses Abschnittes wurde gewünscht von: --77.22.10.106 14:08, 24. Feb. 2023 (CET)