StudySmarter: Besser Lernen
4.5 • +22k Bewertungen
Mehr als 22 Millionen Downloads
Kostenlos
|
|
Quicksort

Wahrscheinlich bist Du im Laufe Deines Lebens schon mal durch eine Drehtür gelaufen. Eine solche Tür besitzt einen Drehpunkt, um den sich die einzelnen Abschnitte drehen. Du fragst Dich, was das mit der Informatik und speziell mit Sortieralgorithmen zu tun haben soll?

Mockup Schule Mockup Schule

Entdecke über 50 Millionen kostenlose Lernmaterialien in unserer App.

Illustration

Lerne mit deinen Freunden und bleibe auf dem richtigen Kurs mit deinen persönlichen Lernstatistiken

Jetzt kostenlos anmelden

Nie wieder prokastinieren mit unseren Lernerinnerungen.

Jetzt kostenlos anmelden
Illustration

Wahrscheinlich bist Du im Laufe Deines Lebens schon mal durch eine Drehtür gelaufen. Eine solche Tür besitzt einen Drehpunkt, um den sich die einzelnen Abschnitte drehen. Du fragst Dich, was das mit der Informatik und speziell mit Sortieralgorithmen zu tun haben soll?

Beim Quicksort Algorithmus sortierst Du Elemente mithilfe eines Dreh- und Angelpunktes – dem sogenannten Pivotelement. Was es damit genau auf sich hat und welche Besonderheiten Quicksort sonst noch hat, erfährst Du hier.

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 gleiche Prinzip verwendet auch der Mergesort Algorithmus. Mehr dazu findest Du in der gleichnamigen Erklärung auf StudySmarter.

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

Das Pivotelement ist nicht weiter definiert, das heißt, Du kannst im Grunde willkürlich ein Element aus Deiner Liste wählen. Oftmals wird jedoch einfach das erste, das letzte oder das mittlere Element gewählt.

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.

"Pivot" kommt aus dem französischen und bedeutet so viel wie "Dreh- und Angelpunkt".

Quicksort Definition

Quicksort ist ein effizientes, vergleichsbasiertes Sortierverfahren, das Datenmengen nach dem Teile-und-Herrsche-Prinzip in Teilprobleme zerteilt, löst und diese dann rekursiv zu einer sortierten Menge zusammenführt.

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.

528497

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.

528497

Tausche nun die 8 mit der 4 aus:

524897

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.

Die Trennlinie ist hier durch ein freies Kästchen in der Tabelle gekennzeichnet.

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.

Die 7 hat dann automatisch ihren endgültigen Platz gefunden und wird nicht weiter mit sortiert.

524798

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.

524

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.

254

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.

245

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.

Beide Bereiche gelten danach als sortiert, da die 8 ein Pivot-Element ist und die 9 das einzige Element im Teilbereich ist.

98

Betrachte anschließend die komplette Liste:

245789

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.

Das Ziel ist es, durch die Wahl des Pivotelements immer zwei möglichst gleich große Teilbereiche zu bekommen.

  • 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(n2).

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.

Variante 2 ist dabei besser geeignet, da Variante 1 den Nachteil hat, dass einzelne Partition-Stufen nicht parallelisiert werden können, bzw. nicht alle Cores ausgenutzt werden.

Quicksort Zusammenfassung

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

Best-CaseAverage-CaseWorst-CasePlatz-komplexitätStabiles Verfahrenvergleichs-basiertIn-PlaceParallelisier-barkeititerativ/rekursiv
O(n log n)O(n log n)O(n2)O(log n)NeinJaJaMöglichRekursiv

Quicksort Vor- und Nachteile

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

Vorteile Nachteile
EffizientRelativ störanfällig
Schnell, vor allem bei größeren DatenmengenEher langsam bei kleineren Datenmengen und bereits vorsortieren Daten
Einfache ImplementationErhöhter Speicherbedarf aufgrund der rekursiven Aufrufe

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

Quicksort – Das Wichtigste

  • Quicksort ist einfach erklärt ein effizientes, vergleichsbasiertes Sortierverfahren, das Datenmengen nach dem Teile-und-Herrsche-Prinzip in Teilprobleme zerteilt und löst. Anschließend führt Quicksort die Daten dann wieder rekursiv zu einer sortierten Menge zusammen.
  • Die Laufzeit von Quicksort beträgt im Best-Case und Average-Case O(n log n) und im Worst-Case O(n2).
  • Quicksort hat verschiedene Pivot-Strategien für die Wahl des Pivotelements:
    • Letztes/Erstes Element

    • Mittleres Element

    • Zufälliges Element

    • Median

  • Der Quicksort Sortieralgorithmus ist nicht stabil.


Nachweise

  1. Helmut Knebl (2021). Algorithmen und Datenstrukturen. Springer Vieweg
  2. Happycoders.eu: Quicksort – Algorithmus, Quellcode, Zeitkomplexität. (14.11.2022)
  3. Matthias Teschner (2012). Algorithmen und Datenstrukturen, Sortieren. cg.informatik.uni-freiburg.de (14.11.2022)

Häufig gestellte Fragen zum Thema Quicksort

Quicksort ist ein effizientes, vergleichsbasiertes Sortierverfahren, das Datenmengen nach dem Teile-und-Herrsche-Prinzip in Teilprobleme zerteilt, löst und diese dann rekursiv zu einer sortierten Menge zusammenführt. 

Quicksort ist ein schnelles Sortierverfahren mit einer Laufzeit von O(n log n) im Best-Case und im Average-Case.

Beim Quicksort Algorithmus werden mithilfe eines Pivotelements Datenmengen in Teilbereiche zerlegt. Diese Teilbereiche werden dann sortiert und je nach Größe der Liste werden so lange neue Pivotelemente gewählt, bis die komplette Liste sortiert ist.  

Quicksort ist kein stabiles Sortierverfahren, weil die Vorgehensweise bei der Unterteilung in die Teilmengen 

nicht gewährleistet, dass gleiche Elemente ihre ursprüngliche Reihenfolge beibehalten.

Teste dein Wissen mit Multiple-Choice-Karteikarten

ErgänzeElemente < Pivotelement, werden in der ______ Teilmenge einsortiert.

ErgänzeElemente > Pivotelement, werden in der ______ Teilmenge einsortiert

Wahr oder falschNach einer Unterteilung des Quicksort ist das vorher gewählte Pivotelement automatisch richtig einsortiert.

Weiter

Schließ dich über 22 Millionen Schülern und Studierenden an und lerne mit unserer StudySmarter App!

Die erste Lern-App, die wirklich alles bietet, was du brauchst, um deine Prüfungen an einem Ort zu meistern.

  • Karteikarten & Quizze
  • KI-Lernassistent
  • Lernplaner
  • Probeklausuren
  • Intelligente Notizen
Schließ dich über 22 Millionen Schülern und Studierenden an und lerne mit unserer StudySmarter App! Schließ dich über 22 Millionen Schülern und Studierenden an und lerne mit unserer StudySmarter App!

Melde dich an für Notizen & Bearbeitung. 100% for free.

Fang an mit StudySmarter zu lernen, die einzige Lernapp, die du brauchst.

Jetzt kostenlos anmelden
Illustration

Entdecke Lernmaterial in der StudySmarter-App