Quicksort je algoritem deli-in-vladaj, ki izbere pivot, elemente razdelimo na tiste manjše in večje od njega, nato rekurzivno sortiramo obе strani. Povprečna vrednost je O(n log n), najslabši primer je O(n²).
Razdeljanje postavi pivot na njegovo končno sortirano pozicijo; vse levo je manjše, vse desno je večje. Rekurzivno delimo obe strani.
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]
(V praksi se uporablja razdeljanje na mestu, da prihranimo pomnilnik.)
| Primer | Čas | Vzrok |
|---|---|---|
| Best/Average | O(n log n) | uravnotežene delitve |
| Worst | O(n²) | že sortirano s slabim pivotom |
Hitro sortiranje na mestu porabi O(log n) prostora za sklad.
Običajno je najhitrejše v praksi zaradi prijaznegosti predpomnilnika in nizke porabe, ter je na mestu. Najslabši primer O(n²) se izogne z naključnim ali mediano-od-treh pivotom. Ni stabilno.
Hitro sortiranje je privzeto v mnogih standardnih knjižnicah zaradi odličnega povprečnega primera in nizke porabe pomnilnika.
Razumevanje, zakaj izbira pivota povzroča najslabši primer O(n²), nas uči ključno lekcijo: povprečni in najslabši primer se lahko ostro razlikujeta.
To je priljubljena tema pri razgovorih prav zaradi te nianse.