Python-Algorithmen

Quicksort (quick sort) in Python

In dieser Lektion implementierst du Quicksort, indem du die Liste um ein Pivotelement (pivot) herum aufteilst.

  • Fortgeschritten
  • 2 Min. Lesezeit
  • 1 ausführbares Beispiel

Einführung

Das Problem

Quicksort ist eine der meistgenutzten Sortierideen, weil er im Durchschnitt schnell und leicht aufzuschreiben ist. Er zeigt eine andere Art, ein Problem zu teilen: nicht in der Mitte, sondern um einen gewählten Wert herum.

Stell es dir so vor

Quicksort ist, als würdest du Bücher nach Höhe um ein ausgewähltes Buch herum sortieren. Jedes niedrigere Buch kommt auf den linken Stapel, jedes höhere auf den rechten, gleich hohe in die Mitte. Dann sortierst du jeden Seitenstapel auf dieselbe Weise und legst die Stapel wieder zusammen.

Von Bücherstapeln zum Code
pivot = values[len(values) // 2]📕 Ein Buch zum Vergleichen wählen
lower = [... if value < pivot]⬅️ Niedrigere Bücher nach links
higher = [... if value > pivot]➡️ Höhere Bücher nach rechts
quick_sort(lower) + equal + quick_sort(higher)📚 Jede Seite sortieren, dann die Stapel zusammenlegen
Um ein Pivot-Element aufteilen, dann jede Seite genauso sortieren.
In einem Satz

Quicksort wählt ein Pivot-Element, teilt die übrigen Elemente in kleinere und größere, sortiert jeden Teil rekursiv und fügt sie zusammen. Im Durchschnitt braucht er O(n log n) Zeit.

Das Wichtigste

  1. if len(values) <= 1: ist der Basisfall: Eine solche Liste ist schon sortiert.
  2. pivot = values[len(values) // 2] nimmt den mittleren Wert als Pivot.
  3. lower, equal und higher teilen die Werte um das Pivot auf; equal hält Duplikate zusammen.
  4. quick_sort(lower) + equal + quick_sort(higher) sortiert beide Seiten und fügt die drei Listen zusammen.

Wann verwendet man das?

  • Partitionieren und Rekursion lernen.
  • Allgemeines In-place-Sortieren in Sprachen und Bibliotheken (mit sorgfältiger Pivot-Wahl).
  • Auswahlprobleme wie das Finden des Medians (Quickselect nutzt dieselbe Aufteilung).

Wann du es nicht brauchst

  • Normaler Python-Code: sorted() ist schneller und stabil.
  • Wenn ein garantierter Worst Case zählt: Schlechte Pivots machen Quicksort zu O(n²), Merge Sort nie.

Quicksort (quick sort) in Python visualisieren

O(n log n)

Mit Start oder Schritt kannst du jeden Vergleich und jede Datenbewegung verfolgen.

Beispielcode

Code ausführen →
main.py
def quick_sort(values):
    if len(values) <= 1:
        return values
    pivot = values[len(values) // 2]
    lower = [value for value in values if value < pivot]
    equal = [value for value in values if value == pivot]
    higher = [value for value in values if value > pivot]
    return quick_sort(lower) + equal + quick_sort(higher)

print(quick_sort([10, 7, 8, 9, 1, 5]))
Run-Button für dieses Beispiel erstellen

Ergebnis der Ausführung

[1, 5, 7, 8, 9, 10]

Erklärung des Codes

Diese gut lesbare Version wählt das mittlere Element als Pivot und erzeugt mit List Comprehensions drei Listen: lower, equal und higher. Das Ergebnis setzt sich aus quick_sort(lower), equal und quick_sort(higher) zusammen. Die durchschnittliche Komplexität ist O(n log n), bei einem ungünstig gewählten Pivot kann der Algorithmus aber auf O(n²) absinken.

Ändere die Werte und führe das Programm im CodeUtility Python Online-Compiler aus, ohne Python lokal zu installieren.

Übungen zur Vertiefung

Ändere den Code anhand der folgenden Vorschläge. Wenn du selbst etwas änderst und das Ergebnis beobachtest, verstehst du viel mehr, als wenn du den Code nur liest.

  1. Teste mit einer leeren Liste, einer Liste mit nur einem Element und einer Liste mit doppelten Werten.
  2. Gib den Zustand nach jedem Schritt aus, um den Algorithmus bei der Arbeit zu beobachten.
  3. Miss die Laufzeit mit 100, 1.000 und 10.000 Elementen und vergleiche sie mit einer anderen Lösung.
Im Python-Compiler ausführen →

Häufige Fehler

Werte gleich dem Pivot verlieren

Mit nur < und > verschwinden Duplikate des Pivots.

Problem
return quick_sort(lower) + [pivot] + quick_sort(higher)
Lösung
return quick_sort(lower) + equal + quick_sort(higher)

Lektion fertig?

Markiere sie als gelernt, um deinen Fortschritt zu verfolgen.

Mit einer Challenge üben

Nutze den Inhalt dieser Lektion, um ein echtes Problem zu lösen. Jede Challenge läuft im Browser, mit sofortigen Tests und einem KI-Review.

Alle Challenges