Quicksort Beispiel
Du möchtest wissen, wie der Quicksort als In-Place-Variante funktioniert? In diesem Artikel zeigen wir dir ein ausführliches Beispiel.
Mit unserem Video verstehst du die einzelnen Schritte des Sortieralgorithmus in kürzester Zeit problemlos!
Inhaltsübersicht
Quicksort Beispiel – In Place
Für die tatsächliche In-Place-Variante nehmen wir dieselbe Liste, wie für das allgemeine Quicksort Beispiel:
[6] [8] [2] [5] [9] [1] [7] [3] [4]
Pivot-Element bestimmen
Als erstes müssen wir ein Pivot-Element bestimmen. Dafür gibt es wie schon vorhin keine allgemeine Regel.
Diesmal gibt es aber noch zusätzlich ein i, welches immer ganz links in der restlichen Zahlenreihe steht. Dazu gibt es dann noch ein j, welches ganz rechts in der Zahlenreihe steht. Das i durchläuft die Zahlenreihe nach rechts und sucht nach Zahlen, die größer als das Pivot-Element sind. Das j sucht im Gegensatz dazu kleinere Werte und läuft dabei nach links.
In unserem Fall ist es direkt passend. Die 8 ist größer und die 4 kleiner als die 6. In dieser Variante tauschen dann diese Zahlen direkt ihren Platz. Das i sucht weiter nach einer größeren Zahl und findet dann die 9 und das j die kleinere Zahl 3. Wir tauschen die beiden. Dann findet das j als Nächstes die 1 und das i als Nächstes 7. Dabei überkreuzen sich die beiden aber, weshalb zu diesem Zeitpunkt der Durchlauf dann immer für den aktuellen Vorgang beendet ist. Dann wird nur noch das j mit dem Pivot-Element getauscht, wenn das j kleiner ist. Die 1 ist kleiner, also kann getauscht werden.
[1] [4] [2] [5] [3] [6] [7] [9] [8]
Wichtig! Wenn unser Pivot-Element am Anfang ganz rechts gewesen wäre, hätten wir es mit unserem i vergleichen müssen! Du hättest also geprüft, ob das i-Element größer als dein Pivot-Element ist. Genauso, wie du in unserem Fall prüfst, ob j kleiner ist. Das kommt daher, weil wir ja durch i und j die restliche Liste schon in größer und kleiner als das Pivot-Element aufgeteilt haben. Unser Pivot-Element muss also folglich in die Mitte.
Zweiter Durchlauf
Aber zurück zur Aufgabe! Damit haben wir also unsere aktuelle Liste [1] [4] [2] [5] [3] [6] [7] [9] [8]. Das Pivot-Element 6 ist damit dann schon auf seiner richtigen Position. Wir können also wieder zwei neue Pivot-Elemente bestimmen. Einmal im linken Bereich bis zur 6 und einmal im rechten Bereich nach der 6. Natürlich nehmen wir dafür wieder in beiden Fällen die erste Zahl, also die 1 und die 7. Wir sortieren auch wieder das i als erstes Element aus der restlichen Liste und j als letztes Element. Dabei aber wieder auf beiden Seiten!
Starten wir also gleich mit dem linken Bereich. Die 4 ist direkt wieder größer, aber keine Zahl ist kleiner als die 1. Damit überkreuzen sich i und j direkt wieder beim Durchlaufen. Damit ist der Durchgang ohne Tausch beendet. Die 1 ist also direkt auf der richtigen Position, da wir ja schon wissen, dass es kein kleineres Element gibt. Auf der rechten Seite sind wieder beide Zahlen größer und damit ist wie vorhin auch schon der Durchlauf beendet. Die 7 ist somit auch offiziell auf dem richtigen Platz.
[1] [4] [2] [5] [3] [6] [7] [9] [8]
Letzte Schritte
Dann beginnen wir wieder von vorn. Diesmal mit der 4 und der 9 als Pivot-Element. Wir wiederholen den Vorgang und tauschen zum Schluss wieder die 4 mit dem aktuellen j, welches nach dem Überkreuzen mit i die 3 ist. Die 9 wird mit der 8 getauscht und beide sind damit auch fertig sortiert.
[1] [3] [2] [4] [5] [6] [7] [8] [9]
Unsere neuen p’s sind nun die 3 und die 5. Die 5 steht allein und ist somit auch richtig positioniert. Also haben wir nur noch die 3 und die 2 zum Sortieren. Damit ist unser letztes Pivot-Element die 2.
[1] [2] [3] [4] [5] [6] [7] [8] [9]
[1] [2] [3] [4] [5] [6] [7] [8] [9]
[1] [2] [3] [4] [5] [6] [7] [8] [9]
Jetzt sind wir dann auch endlich fertig! Zum Schluss haben wir wieder unsere sortierte Liste.