Das Standard-Quicksort (Letzte Aktualisierung: 4. August 2025 um 12:30:25 Uhr) Daten Name:  Quicksort Autor:  Sir Charles Antony Richard Hoare Veröffentlichung:  1960 Arbeitsweise:  - Teile-und-herrsche - vergleichsbasierend - In-Place rekursiv:  ja stabil:  nein      Inhaltsverzeichnis 1.  Beschreibung 2.  Funktionsprinzip 3.  Grundsätzliche Probleme 4.  Der Quellcode Beschreibung Das originale Quicksort wurde im Jahr 1960 von dem englischen Informatiker "Sir Charles Antony Richard Hoare" entwickelt. Seitdem wurde das Funktionsprinzip von vielen Informatikern immer wieder verbessert und weiterentwickelt. Oben Funktionsprinzip Quicksort basiert auf dem Funktionsprinzip des Teile-und-herrsche-Verfahrens. Quicksort wählt hierbei ein Element für die Teilung (Pivot) aus und teilt den aktuellen Arbeitsbereich im Array in eine linke und rechte Teilliste (Hälfte). Meistens verwenden viele Informatiker hierfür das letzte Element, was - wie es im nachfolgenden Abschnitt "Grundsätzliche Probleme" erklärt wird - aber ein systematischer Fehler ist, der zum Absturz oder einer unglaublich langen Sortierdauer führen kann. In der linken Teilliste befinden sich für gewöhnlich die Elemente, die kleiner als das Vergleichselement sind und in der rechten Teilliste befinden sich die, die größer oder mit dem Vergleichselement identisch sind. Nach der Teilung wird das Vergleichselement vom Ende des aktuellen Arbeitsbereichs, mit dem Anfang der rechten Teilliste vertauscht. Sollte es in der linken Teilliste mehr als ein Element geben, dann startet sich Quicksort in dieser Teilliste als weitere Rekursion erneut. Das Gleiche gilt auch für die rechte Teilliste, wenn es dort mehr als zwei Elemente geben sollte. Die neue rechte Rekursion startet dann auf dem Element, das sich rechts vom Vergleichselement befindet. Quicksort teilt auf diese Art und Weise das Array in immer kleiner werdende Teillisten auf, bis am Ende das ganze Array sortiert ist. Der Nachteil von Quicksort besteht darin, dass die Sortierung nicht stabil durchgeführt wird, weil die zu sortierenden Elemente über große Entfernungen im Array hinweg, direkt miteinander vertauscht werden. Für eine stabile Sortierung, müssten sich alle identischen Elemente nach der Sortierung immer noch in der gleichen Reihenfolge befinden, wie vor der Sortierung. Der Art und Weise wie man als Informatiker Quicksort Programmieren kann, sind keine Grenzen gesetzt. Das Standard-Quicksort, das wohl am weitesten bekannt ist und das weiter unten als Quellcode zu sehen ist, ist aber ganz klar eine schlechte und sehr langsam arbeitende Lösung, weil sie extrem viele Vergleiche für die Sortierung benötigt. Der Quellcode besteht aus einer "DO-LOOP-Schleife", die sich so lange wiederholt, bis die Teilung abgeschlossen ist. Das ist dann der Fall, wenn die Variablen "I" und "J", die für den linken und rechten Rand des aktuellen Arbeitsbereiches stehen, aneinander vorbeigelaufen sind. Bei jedem Durchlauf der Schleife, müssen immer 12 Vergleiche durchgeführt werden und die Anzahl der Durchläufe der Schleife, kann je nach Datenstruktur mit der Anzahl der Elemente im aktuellen Arbeitsbereich identisch sein. Nach der Teilung kommen dann noch zwei weitere Vergleiche für das eventuelle starten der nächsten Rekursionen hinzu. Selbst bei nur 1000 zu sortierenden Elementen, kommen so im Durchschnitt knapp 91.000 Vergleiche zusammen. Andere Teile-und-herrsche-Verfahren, wie zum Beispiel der "Stabilisator" von Babylonsort, benötigen hier nur etwas weniger als 19.000 Vergleiche, also knapp fünf Mal weniger. Oben Grundsätzliche Probleme Bei einem Teile-und-herrsche-Verfahren muss man grundsätzlich immer das mittlere Element für die Teilung (Pivot) verwenden und es gleich zu Beginn mit dem letzten vertauschen. Der standardmäßige systematische Fehler beim Programmieren von Quicksort oder anderen Teile-und-herrsche-Verfahren ist aber der, dass es immer wieder zu dem Irrtum kommt, dass es angeblich egal wäre, welches Element man für die Teilung verwendet. Zugegeben: Wenn es sich um ein zufällig gemischtes Array handelt, dann wird sich jedes ausgewählte Element auch nur zufällig auf die Geschwindigkeit und Effektivität der Sortierung auswirken. Ganz anders sieht es aber aus, wenn Quicksort ein Array sortieren soll, bei dem einer der zwei folgenden Fälle vorliegt: 1. Best-Case: Im Array gibt es kein Element, das kleiner als das vorherige ist. 2. Worst-Case: Im Array gibt es kein Element, das größer als das vorherige ist. Würde man nur in einem dieser beiden Fälle das erste oder letzte Element für die Teilung verwenden, dann würde die Anzahl der gleichzeitig aktiven Rekursionen, bis auf die Anzahl der zu sortierenden Elemente ansteigen, was bei großen Arrays dann unweigerlich zum Absturz von Quicksort führt, weil es zum Überlauf des Stapelspeichers der Rekursionen kommt. Die Anzahl der Rekursionen ist begrenzt! Die Anzahl der Rekursionen die gleichzeitig aktiv sein können, ist selbstverständlich begrenzt, auch wenn viele Informatiker dies scheinbar immer wieder vergessen. Anfang des Jahrtausends konnte man zum Beispiel im "Visual Basic" von Excel noch bis zu 5000 Rekursionen gleichzeitig aktiv sein lassen. Irgendwann zwischen Sommer 2021 und Mitte März 2022, wurde die Größe dieses Stapelspeichers durch Microsoft auf 2748 reduziert. Im "Office 2021" sollen es aktuell sogar nur noch um die 156 sein. (Der genaue Wert wird vom Autor nachgereicht, sobald sein schneller Computer aus der Reparatur zurückgekommen ist.) Der böse "Identical-Case": Was für Teile-und-herrsche-Verfahren ebenfalls ein sehr großes Problem ist und auch bei der Verwendung des mittleren Elements unweigerlich zum Absturz führt, das ist der "Identical-Case", bei dem alle zu sortierenden Elemente identisch sind. Einen derartigen Absturz kann man zum Beispiel auf die folgende Art und Weise vermeiden: Nach der Teilung wird überprüft, ob es keine kleineren Elemente gibt. In diesem Fall setzt man, wenn es mehr als drei Elemente gibt, den linken Rand eine Position nach rechts und startet die Rekursion erneut, indem man den Programmablauf irgendwie zum Anfang zurückkehren lässt. Entweder mit dem so schönen "GOTO"-Befehl, oder indem man eine zusätzliche Schleife verwendet, die in diesem Fall ein weiteres Mal ausgeführt wird. Eine wesentlich bessere Lösung ist aber die, den aktuellen Arbeitsbereich im Array, immer in drei Teillisten zu unterteilen (kleiner, identisch, größer). Wenn es nämlich sehr viele identische Elemente geben sollte, dann führt das zu einer ganz massiven Beschleunigung der Sortierung. Und in dem Fall, dass alle zu sortierenden Elemente identisch sein sollten, ist die ganze Sortierung sogar bereits nach der ersten Teilung beendet. Das Problem mit der Laufzeit: Neben dem Problem dass es zu einem Überlauf des Stapelspeichers der Rekursionen kommen kann, gibt es noch einen anderen Grund dafür, warum man das erste und letzte Element nicht für die Teilung verwenden darf: Selbst wenn man das Problem mit den Abstürzen vermeiden kann, dann gibt es immer noch das Problem mit der Laufzeit. Wenn Quicksort im Best- oder Worst-Case genauso viele Teilungen durchführen muss, wie es zu sortierende Elemente gibt, dann kann die Sortierung bei größeren Arrays unglaublich lange dauern. Herr Oppermann - der Autor dieser Internetseite - hat in einem Test einmal die Zeit gemessen, die sein schnellster Computer innerhalb von Excel benötigt, um mit einem Makro eine Milliarde Zahlen im Best-Case zu teilen. Um die Dauer der gesamten Sortierung hochzurechnen, wurde diese Zeit dann mit einer Milliarde multipliziert und durch zwei geteilt. Ergebnis: Quicksort würde 459,48 Jahre für die Sortierung benötigen. Wählt man hingegen das mittlere Element für die Teilung aus, dann dauert die Sortierung nur noch 8 Minuten und 10 Sekunden. Die Ursache für diesen Zeitunterschied liegt darin, weil bei einem Teile-und-herrsche-Verfahren im Idealfall die beiden Teillisten nur noch halb so groß sind, wie der vorherige Arbeitsbereich. Damit geht jede weitere Teilung dann auch in etwa doppelt so schnell, wie die vorherige. Diese exponentielle Beschleunigung sollte daher ein guter Beleg dafür sein, warum man bei einem Teile-und-herrsche-Verfahren grundsätzlich immer das mittlere Element für die Teilung verwenden muss und kein anderes. Aber auch ein zufällig ausgewähltes Element, ist selbst bei einem zufällig gemischten Array, keine praktikable Lösung. Oben Der Quellcode Weil immer wieder der systematische Fehler gemacht wird, standardmäßig das letzte Element für die Teilung (Pivot) zu verwenden, ist dieser Fehler auch im nachfolgenden Quellcode zu sehen: Sub Quicksort(lngL As Long, lngR As Long) Dim lngI As Long Dim lngJ As Long Dim lngP As Long Dim lngTEMP As Long lngI = lngL lngJ = lngR - 1 lngP = lngArray(lngR) Do If lngArray(lngI) < lngP Then lngI = lngI + 1 If lngArray(lngJ) >= lngP Then lngJ = lngJ - 1 If lngArray(lngI) >= lngP And lngArray(lngJ) < lngP And lngI < lngJ Then         lngTEMP = lngArray(lngI)         lngArray(lngI) = lngArray(lngJ)         lngArray(lngJ) = lngTEMP         lngI = lngI + 1         lngJ = lngJ - 1 End If Loop Until lngI > lngJ lngTEMP = lngArray(lngI) lngArray(lngI) = lngArray(lngR) lngArray(lngR) = lngTEMP If lngI - lngL > 1 Then Quicksort lngL, lngJ If lngR - lngI > 1 Then Quicksort lngI + 1, lngR End Sub Home / Oben / Impressum / Datenschutzerklärung   Diese Internetseite wurde für eine Auflösung von 2160 x 1440 Bildschirmpunkten und eine Anzeige-Skalierung von 150% optimiert.