Quicksort to algorytm sortowania typu "dziel i zwyciężaj", który wybiera pivot, partycjonuje elementy na mniejsze i większe od niego, a następnie rekurencyjnie sortuje obie strony. Średnio O(n log n), najgorszy przypadek O(n²).
Partycjonowanie umieszcza pivot na jego ostatecznej pozycji w posortowanej tablicy; wszystko po lewej stronie jest mniejsze, wszystko po prawej większe. Rekurencyjnie powtórz dla obu stron.
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]
(W praktyce stosuje się partycjonowanie w miejscu, aby oszczędzić pamięć.)
| Przypadek | Czas | Przyczyna |
|---|---|---|
| Najlepszy/Średni | O(n log n) | zbalansowane partycje |
| Najgorszy | O(n²) | już posortowana tablica z złym pivotem |
Quicksort w miejscu zużywa O(log n) miejsca na stosie.
Zwykle najszybszy w praktyce ze względu na przyjazność dla cache'u i niskie obciążenie, i działa w miejscu. Najgorszy przypadek O(n²) unika się przez losowy lub median-of-three pivot. Nie jest stabilny.
Quicksort jest domyślny w wielu bibliotekach standardowych ze względu na doskonałą szybkość średnią i niskie zużycie pamięci.
Zrozumienie, dlaczego wybór pivotu powoduje najgorszy przypadek O(n²), uczy ważną lekcję: przypadek średni i najgorszy mogą się znacząco różnić.
To ulubiony temat rozmów kwalifikacyjnych właśnie ze względu na tę subtelność.