Video anzeigen

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!

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

Du bist gerade auf der Suche nach einem dualen Studium oder Ausbildungsplatz? Wir von Studyflix helfen dir weiter. Im Studyflix Ausbildungsportal warten über 20.000 freie Plätze auf dich. Schau doch mal vorbei.

Du willst wissen, wofür du das Thema Quicksort Beispiel lernst? Über das Studyflix Jobportal kannst du dich auf die Suche nach Praxiserfahrung begeben. Hier warten über 20.000 Praktika, Werkstudentenstellen, Einstiegsjobs und auch Abschlussarbeiten auf dich. Schau doch mal vorbei.

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.

Softwaretechnik
Sortieralgorithmen
 – Video

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.