Quicksort er en divide-and-conquer-sorteringsalgoritme, der vælger et pivot, opdeler elementer i dem, der er mindre og større end det, og sorterer derefter hver side rekursivt. Gennemsnit O(n log n), værste tilfælde O(n²).
Opdeling placerer pivot i dets endelige sorterede position; alt til venstre er mindre, alt til højre er større. Kør rekursivt på begge sider.
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 partitionering bruges i praksis for at spare hukommelse.)
| Tilfælde | Tid | Årsag |
|---|---|---|
| Bedste/Gennemsnit | O(n log n) | balancerede opdelinger |
| Værste | O(n²) | allerede sorteret med dårligt pivot |
In-place quicksort bruger O(log n) stakplads.
Sædvanligvis hurtigst i praksis på grund af cache-venlig design og lav overhead, og det er in-place. Det værste tilfælde O(n²) undgås med et randomiseret eller median-of-three pivot. Det er ikke stabilt.
Quicksort er standard i mange biblioteker på grund af dets fremragende gennemsnitlige hastighed og lave hukommelsesomkostninger.
At forstå, hvorfor pivotvalg forårsager det værste tilfælde O(n²), lærer en vigtig lektie: gennemsnit og værste tilfælde kan afvige markant.
Det er et yndet interviewemne netop på grund af denne nuance.