Quicksort is een divide-and-conquer sorteeralgoritme dat een pivot kiest, elementen partitioneert in degenen die kleiner en groter zijn dan de pivot, en vervolgens elke kant recursief sorteert. Gemiddeld O(n log n), worst case O(n²).
Partitionering plaatst de pivot in zijn uiteindelijke gesorteerde positie; alles links is kleiner, alles rechts is groter. Recursief verwerken op beide zijden.
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 wordt in de praktijk gebruikt om geheugen te besparen.)
| Geval | Tijd | Oorzaak |
|---|---|---|
| Best/Gemiddeld | O(n log n) | gebalanceerde partities |
| Worst | O(n²) | al gesorteerd met slechte pivot |
In-place quicksort gebruikt O(log n) stack ruimte.
Usually the fastest in practice dankzij cache-vriendelijkheid en lage overhead, en het is in-place. Het O(n²) worst case wordt vermeden met een gerandomiseerde of median-of-three pivot. Het is niet stabiel.
Quicksort is standaard in veel bibliotheekimplementaties vanwege de uitstekende gemiddelde snelheid en laag geheugengebruik.
Begrijpen waarom pivot keuze het O(n²) worst case veroorzaakt leert een belangrijke les: gemiddeld en worst case kunnen sterk verschillen.
Het is een favoriet interviewonderwerp juist vanwege die nuance.