Quicksort ist ein Divide-and-Conquer-Sortieralgorithmus, der ein Pivot auswählt, Elemente in solche kleiner und größer als dieses unterteilt und dann jede Seite rekursiv sortiert. Durchschnitt O(n log n), schlimmster Fall O(n²).
Die Partitionierung platziert das Pivot an seiner endgültigen sortierten Position; alles links ist kleiner, alles rechts ist größer. Rekursiv auf beide Seiten anwenden.
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2] # pick a pivot
left = [x for x in arr if x < pivot] # smaller
mid = [x for x in arr if x == pivot] # equal
right = [x for x in arr if x > pivot] # larger
return quicksort(left) + mid + quicksort(right)
quicksort([5, 2, 8, 1, 3]) # -> [1, 2, 3, 5, 8]
(In-place-Partitionierung wird in der Praxis verwendet, um Speicher zu sparen.)
| Fall | Zeit | Ursache |
|---|---|---|
| Beste/Durchschnitt | O(n log n) | ausgewogene Partitionen |
| Schlechtester | O(n²) | bereits sortiert mit schlechtem Pivot |
In-place Quicksort benötigt O(log n) Stack-Platz.
Gewöhnlich der schnellste in der Praxis aufgrund von Cache-Freundlichkeit und nierigem Overhead, und es ist in-place. Der schlimmste Fall O(n²) wird mit einem randomisierten oder median-of-three Pivot vermieden. Es ist nicht stabil.
Quicksort ist der Standard in vielen Standardbibliotheken wegen seiner hervorragenden durchschnittlichen Geschwindigkeit und niedrigen Speichernutzung.
Zu verstehen, warum die Pivot-Wahl den schlimmsten Fall O(n²) verursacht, lehrt eine wichtige Lektion: Durchschnitt und schlimmster Fall können stark auseinandergehen.
Es ist ein beliebtes Interviewthema genau wegen dieser Nuance.