Theoretische Informatik

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 gerade eben 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 auch schon vorhin keine allgemeine Regel.

Diesmal gibt es aber noch zusätzlich ein i, welches immer ganz links in der restlichen Zahlenreihe steht. Und dazu gibt es dann auch noch ein j, welches ganz rechts in der Zahlenreihe steht. Das 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 auch nach links.

Quicksort Beispiel In Place
direkt ins Video springen
Quicksort Beispiel

In unserem Fall ist es direkt passend. Die 8 ist größer und die 4 kleiner als die 6. Und 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 die 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 und zu diesem Zeitpunkt ist der Durchlauf dann immer für den aktuellen Vorgang beendet. 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 auch schon auf seiner richtigen Position. Wir können also wieder 2 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 mal wieder 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 und 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 und die 7 ist damit 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 da 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]

Und jetzt sind wir dann auch endlich fertig! Zum Schluss haben wir wieder unsere sortierte Liste.

Hallo, leider nutzt du einen AdBlocker.

Auf Studyflix bieten wir dir kostenlos hochwertige Bildung an. Dies können wir nur durch die Unterstützung unserer Werbepartner tun.

Schalte bitte deinen Adblocker für Studyflix aus oder füge uns zu deinen Ausnahmen hinzu. Das tut dir nicht weh und hilft uns weiter.

Danke!
Dein Studyflix-Team

Wenn du nicht weißt, wie du deinen Adblocker deaktivierst oder Studyflix zu den Ausnahmen hinzufügst, findest du hier eine kurze Anleitung. Bitte lade anschließend die Seite neu.