Quicksort er en dele-og-hersk sorteringsalgoritme som velger en pivot, partisjonerer elementer i de som er mindre og større enn den, og sorterer deretter hver side rekursivt. Gjennomsnitt O(n log n), verste tilfelle O(n²).
Partisjonering plasserer pivotelementet i sin endelige sorterte posisjon; alt til venstre er mindre, alt til høyre er større. Gjenta 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 partisjonering brukes i praksis for å spare minne.)
| Tilfelle | Tid | Årsak |
|---|---|---|
| Best/Gjennomsnitt | O(n log n) | balanserte partisjoner |
| Verst | O(n²) | allerede sortert med dårlig pivot |
In-place quicksort bruker O(log n) stack-plass.
Gjennomgående raskeste i praksis på grunn av cache-vennlighet og lav overhead, og det er in-place. Det verste tilfellet O(n²) unngås med en randomisert eller median-of-three pivot. Det er ikke stabilt.
Quicksort er standard i mange bibliotekimplementasjoner på grunn av den utmerkede gjennomsnittsfarten og lavt minne bruk.
Å forstå hvorfor pivotvalg forårsaker det verste tilfellet O(n²) lærer en viktig leksjon: gjennomsnitt og verste tilfelle kan avvike skarpt.
Det er et favorittintervjutema nettopp på grunn av den nansen.