Quicksort je sort temeljen na principu "podijeli pa vladaj" koji bira pivot, dijeli elemente na one manje i veće od njega, te zatim rekurzivno sortira obje strane. Prosječna složenost je O(n log n), a najgori slučaj je O(n²).
Particioniranje postavlja pivot na njegovu završnu sortiranu poziciju; sve lijevo je manje, sve desno je veće. Rekurzivno obradite obje strane.
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 particioniranje se koristi u praksi kako bi se uštedjela memorija.)
| Slučaj | Vrijeme | Razlog |
|---|---|---|
| Najbolji/Prosječan | O(n log n) | uravnotežene particije |
| Najgori | O(n²) | već sortiran sa lošim pivotom |
In-place quicksort koristi O(log n) prostora na stack-u.
Obično najbrži u praksi zahvaljujući cache-friendly svojstvima i maloj overhead-u, te je in-place. O(n²) najgori slučaj se izbjegava sa randomiziranim ili median-of-three pivotom. Nije stabilan.
Quicksort je zadana opcija u mnogim standardnim bibliotekama zbog odličnih prosječnih performansi i male potrošnje memorije.
Razumijevanje zašto izbor pivota uzrokuje O(n²) najgori slučaj poučava važnu lekciju: prosječan i najgori slučaj mogu se drastično razlikovati.
To je omiljen tema na intervjuima upravo zbog te nijanse.