Quicksort

Quicksort einfach erklärt

Quicksort ist ein Sortieralgorithmus, der nach dem "divide and conquer" Prinzip arbeitet. Nach dem Teile-und-Herrsche-Prinzip werden Probleme in Teilprobleme zerlegt, diese dann gelöst und anschließend wieder zusammengesetzt.

Das Prinzip hinter Quicksort ist es, eine Datenmenge in Teilmengen zu unterteilen. Dafür wird vorher ein Pivotelement oder auch Pivot-Element festgelegt.

• Elemente kleiner des Pivot-Elements werden in der linken Teilmenge einsortiert
• Elemente größer des Pivot-Elements werden in der rechten Teilmenge einsortiert

Bei jedem Unterteilen der Datenmenge wird wieder ein neues Pivot-Element festgelegt. Sind alle Teilbereiche sortiert, endet auch die Sortierung, da sich die Liste dann in der richtigen Reihenfolge befindet.

Quicksort Definition

Wie der Quicksort Algorithmus dabei genau vorgeht, siehst Du im nachfolgenden Beispiel.

Quicksort Visualisierung

Quicksort lässt sich am einfachsten an einem Beispiel verdeutlichen. Gegeben ist ein Array [5, 2, 8, 4, 9, 7].

Schritt 1: Pivot-Element festlegen

Zunächst musst Du das Pivotelement festlegen. Die einfachste Variante ist dabei, das Element ganz rechts zu wählen, in diesem Fall also die 7.

Schritt 2: Elemente suchen und vertauschen

Jetzt wird geschaut, welche Elemente kleiner und welche größer sind als die 7 sind. Kleinere werden links einsortiert, größere rechtes. Dazu gehst Du die Liste schrittweise erst von links und dann von rechts durch und vergleichst die Elemente jeweils mit dem gewählten Pivot-Element.

Von links beginnend schaust Du welches Element größer oder gleich der 7 ist – das ist hier die 8. Gucke dann von rechts welches Element kleiner ist als die 7, das Pivot-Element selbst überspringst Du bei der Suche – Du landest bei der 4.

Tausche nun die 8 mit der 4 aus:

Bei einer größeren Liste würdest Du diesen Schritt so lange weiter durchführen, bis die imaginären Zeiger direkt nebeneinander liegen. In diesem Fall liegen die Zeiger bereits auf der 4 und der 8 – zwischen diesen beiden Zahlen kannst Du eine imaginäre Trennlinie einfügen. Zu diesem Zeitpunkt sind alle Elemente links kleiner als 7 und alle rechts größer oder gleich 7.

Was Du jetzt noch machen musst, ist Folgendes: Alle Elemente links der Trennlinie sind kleiner 7 und alle rechts größer oder gleich. Deswegen kannst Du davon ausgehen, dass die 7 im rechten Bereich das kleinste oder eines der kleinsten Elemente sein muss (falls es mehrere Elemente mit dem Wert 7 gibt). Tausche nun also die 7 mit der 8.

Schritt 3: Wiederholen von Schritt 1 und 2

Wiederhole nun die Schritte 1 und 2 bis die Liste vollständig sortiert ist. Dabei betrachtest Du die übrig gebliebenen Teilbereiche jeweils getrennt voneinander. Beginne mit dem linken Bereich und lege auch hier das Element ganz rechts als Pivot-Element fest, sprich die 4.

Suche jetzt wieder, beginnend von links, nach dem ersten Element, dass größer oder gleich 4 ist und von rechts nach dem ersten Element, dass kleiner als 4 ist. Dementsprechend müssen die 5 und die 2 miteinander vertauscht werden – zwischen ihnen kannst Du wieder eine Trennlinie ziehen.

Vertausche anschließend die 5 noch mit der 4 – die 4 liegt im Anschluss wieder auf ihrer endgültigen Position. Da sowohl der linke als auch der rechte Teilbereich neben der 4 nur noch ein Element enthalten, gelten diese Bereiche ebenfalls als sortiert.

Betrachte jetzt noch den rechten Teilbereich neben dem ersten gewählten Pivotelement (7). Lege auch hier wieder das rechte Element als neues Pivotelement fest. Beim Durchgehen der Liste von links wird Dir auffallen, dass die 9 größer ist als die 8 – von rechts gibt es kein Element, dass kleiner ist. Vertausche also die 9 und die 8 miteinander.

Betrachte anschließend die komplette Liste:

Wie Du siehst, sind die Daten nun vollständig sortiert und der Quicksort Algorithmus ist somit beendet.

Quicksort Vorgehensweise

Noch einmal in Kurzform, wie geht der Quicksort Algorithmus beim Sortieren von Datenmengen vor?

• Wähle ein Pivot-Element

• Sortiere die Teilbereiche links und rechts vom Pivot-Element

  • Nach links: Elemente < Pivot-Element

  • Nach rechts: Elemente > Pivot-Element

  • Am Ende befindet sich das aktuelle Pivot-Element an der richtigen Stelle

• Führe den vorherigen Schritt so lange durch, bis es nur noch Pivot-Elemente und Teilbereiche mit einem Element gibt – dann gilt die Liste als vollständig sortiert

Pivot-Strategie

Die Wahl des Pivotelements ist kein unwichtiger Faktor, da es die Geschwindigkeit des Algorithmus beeinflussen kann. Bei der Wahl gibt es verschiedene Strategien.

• Letztes Element

• Erstes Element

• Mittleres Element

• Zufälliges Element

• Median

Im Beispiel wurde die Pivot-Strategie "letztes Element" verwendet. Diese macht den Algorithmus besonders einfach, allerdings macht sie ihn in der Praxis auch langsamer – gleiches gilt für die Strategie "Erstes Element". Vor allem bei vorsortierten Datenmengen bereiten die beiden Strategien Probleme. Das liegt daran, dass beim Teilen nicht zwei nahezu gleich große Teilbereiche entstehen, sondern im Grunde nur ein großer, da der andere jeweils leer ist.

Beim Median musst Du beachten, nicht den Median der kompletten Datenmenge zu bilden, denn dafür müsstest Du die Datenmenge zunächst sortieren. Stattdessen würdest Du jeweils den Median von drei, fünf oder noch mehr Elementen bilden.

Quicksort Komplexität

Die Komplexität von Quicksort muss getrennt in die Laufzeit (Zeitkomplexität) und den Speicheraufwand (Platzkomplexität) betrachtet werden.

Quicksort Laufzeit

Quicksort erreicht im Best-Case eine Laufzeit von O(n log n). Der Best-Case liegt vor, wenn eine Datenmenge immer wieder in zwei gleich große Teilmengen zerlegt werden kann. Der Average-Case lässt sich nicht ohne einen umfangreichen mathematischen Beweis herleiten. Dabei kommt heraus, dass auch die durchschnittliche Zeitkomplexität noch quasi-linear ist – also O(n log n) beträgt.

In den Worst-Case fallen vor allem aufsteigend oder absteigend vorsortierte Datenmengen. Wird dabei immer das Element ganz links oder ganz rechts als Pivot-Element gewählt (also das kleinste oder das größte), würde man die Daten nicht in zwei gleich große Teilmengen unterteilen. Entsprechend beträgt die Zeitkomplexität dann O(n²).

Quicksort Platzkomplexität

Quicksort wird in-place mit einem konstanten zusätzlichen Speicheraufwand von O(log n) sortiert.

Quicksort – Weitere Begrifflichkeiten

Weitere Begriffe, die rund um Quicksort noch geklärt werden sollen, sind:

• Stabilität

• Vergleichsbasiert

• Iterativ vs. rekursiv

• Parallelisierbarkeit

Quicksort stabil

Quicksort ist kein stabiles Sortierverfahren. Warum? Die Vorgehensweise bei der Unterteilung in die Teilmengen kann nicht gewährleisten, dass gleiche Elemente ihre ursprüngliche Reihenfolge beibehalten.

Quicksort vergleichsbasiert

Da Quicksort immer zwei Elemente miteinander vergleicht, handelt es sich um einen vergleichsbasierten Sortieralgorithmus.

Quicksort rekursiv

Beim Quicksort Sortieralgorithmus handelt es sich um ein rekursives Verfahren, da die Teilprobleme in der Regel rekursiv aufgerufen werden.

Quicksort Parallelisierbarkeit

Beim Quicksort Algorithmus gibt es verschiedene Möglichkeiten für eine Parallelisierung.

• Variante 1: Einzelne Partitionen können noch weiter parallel partitioniert werden.
• Variante 2: Eine Partition von mehreren Cores parallel partitionieren.

Quicksort Zusammenfassung

In der folgenden Tabelle findest Du eine Zusammenfassung des bisher gelernten:

Quicksort Vor- und Nachteile

Verschiedene Vor- und Nachteile von Quicksort findest Du in der folgenden Übersicht:

Um die Nachteile von Quicksort zu umgehen, gibt es verschiedene Möglichkeiten den Algorithmus entsprechend anzupassen.

Quicksort Verbesserungen

Eine Verbesserungsmöglichkeit liegt bei der Pivot-Strategie. Du solltest es vermeiden, ein schlechtes Pivotelement zu wählen, da das die Laufzeit verlängert. Um den Worst-Case bei der Laufzeit zu vermeiden, eignet sich eine randomisierte Wahl des Pivot-Elements am ehesten – einfach, weil dabei die Wahrscheinlichkeit, dass Du den Worst-Case vermeidest, so am größten ist.

Weitere Möglichkeiten für eine Verbesserung vom Quicksort Algorithmus:

• Kombination von Quicksort und Insertion Sort, da Insertion Sort für kleine Datenmengen der bessere Sortieralgorithmus ist. Bis zu einer bestimmten Größe wird also mit Insertion Sort anstatt Quicksort sortiert.
• Dual-Pivot – statt eines Pivotelements wählst Du zwei aus. Der restliche Algorithmus läuft dann wie gehabt ab.
• Datenmenge vor dem Sortieren mischen, damit eine zufällige Anordnung der Elemente vorliegt.

Quicksort Beispiel

Es folgt noch ein weiteres (Code-)Beispiel zum Quicksort Algorithmus.

Quicksort Pseudocode

Möglicher Pseudocode könnte bei Quicksort wie folgt aussehen:

funktion quicksort (links, rechts)

if links < rechts
    t = teilen(links, rechts)
    quicksort(links, t)
    quicksort(t + 1, rechts)
  end
end

funktion teilen(links, rechts)
  
  n = links – 1
  m = rechts + 1

  pivot = Liste[(links + rechts) / 2]
  while Liste[n] < pivot  // wenn Elemente < Pivot-Element ordne sie links ein
    n++
  while Liste [m] > pivot  // wenn Elemente > Pivot-Element ordne sie rechts ein
    m++

  if (n < m)
    int a = Liste[n]
    Liste[n] = Liste[m]
    Liste[m] = a
  else return m