Quicksort (quick sort) in Python
In dieser Lektion implementierst du Quicksort, indem du die Liste um ein Pivotelement (pivot) herum aufteilst.
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.
pivot = values[len(values) // 2]📕 Ein Buch zum Vergleichen wählenlower = [... if value < pivot]⬅️ Niedrigere Bücher nach linkshigher = [... if value > pivot]➡️ Höhere Bücher nach rechtsquick_sort(lower) + equal + quick_sort(higher)📚 Jede Seite sortieren, dann die Stapel zusammenlegenQuicksort 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
if len(values) <= 1:ist der Basisfall: Eine solche Liste ist schon sortiert.pivot = values[len(values) // 2]nimmt den mittleren Wert als Pivot.lower,equalundhigherteilen die Werte um das Pivot auf;equalhält Duplikate zusammen.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
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]))
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.
- Teste mit einer leeren Liste, einer Liste mit nur einem Element und einer Liste mit doppelten Werten.
- Gib den Zustand nach jedem Schritt aus, um den Algorithmus bei der Arbeit zu beobachten.
- Miss die Laufzeit mit 100, 1.000 und 10.000 Elementen und vergleiche sie mit einer anderen Lösung.
Häufige Fehler
Werte gleich dem Pivot verlieren
Mit nur < und > verschwinden Duplikate des Pivots.
return quick_sort(lower) + [pivot] + quick_sort(higher)
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