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?

Quicksort Quicksort

Erstelle Lernmaterialien über Quicksort mit unserer kostenlosen Lern-App!

  • Sofortiger Zugriff auf Millionen von Lernmaterialien
  • Karteikarten, Notizen, Übungsprüfungen und mehr
  • Alles, was du brauchst, um bei deinen Prüfungen zu glänzen
Kostenlos anmelden
Inhaltsverzeichnis
Inhaltsangabe

    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

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

    Wie schnell ist Quicksort? 

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

    Wie funktioniert Quicksort? 

    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.  

    Ist Quicksort stabil? 

    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

    Entdecken Lernmaterialien mit der kostenlosen StudySmarter App

    Kostenlos anmelden
    1
    Über StudySmarter

    StudySmarter ist ein weltweit anerkanntes Bildungstechnologie-Unternehmen, das eine ganzheitliche Lernplattform für Schüler und Studenten aller Altersstufen und Bildungsniveaus bietet. Unsere Plattform unterstützt das Lernen in einer breiten Palette von Fächern, einschließlich MINT, Sozialwissenschaften und Sprachen, und hilft den Schülern auch, weltweit verschiedene Tests und Prüfungen wie GCSE, A Level, SAT, ACT, Abitur und mehr erfolgreich zu meistern. Wir bieten eine umfangreiche Bibliothek von Lernmaterialien, einschließlich interaktiver Karteikarten, umfassender Lehrbuchlösungen und detaillierter Erklärungen. Die fortschrittliche Technologie und Werkzeuge, die wir zur Verfügung stellen, helfen Schülern, ihre eigenen Lernmaterialien zu erstellen. Die Inhalte von StudySmarter sind nicht nur von Experten geprüft, sondern werden auch regelmäßig aktualisiert, um Genauigkeit und Relevanz zu gewährleisten.

    Erfahre mehr
    StudySmarter Redaktionsteam

    Team Informatik Lehrer

    • 10 Minuten Lesezeit
    • Geprüft vom StudySmarter Redaktionsteam
    Erklärung speichern

    Lerne jederzeit. Lerne überall. Auf allen Geräten.

    Kostenfrei loslegen

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

    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!

    Alle Inhalte freischalten mit einem kostenlosen StudySmarter-Account.

    • Sofortiger Zugriff auf Millionen von Lernmaterialien.
    • Karteikarten, Notizen, Übungsprüfungen, AI-tools und mehr.
    • Alles, was du brauchst, um bei deinen Prüfungen zu bestehen.
    Second Popup Banner