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 AnfangVgl do Dec(Rechts); if LinksRechts; QSort(Anfang,Rechts); QSort(Links,Ende) end end; procedure QSort(Anfang,Ende:integer); var Links,Rechts,Vgl,H:integer; begin if Anfang=Vgl; repeat Dec(Rechts) until Zahl[Rechts]=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 AnfangZahl[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]=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 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. -- 23:43, 19. Jun. 2008 (CEST) J.Adolf