Quicksort on divide-and-conquer-lajittelualgoritmi, joka valitsee pivot-elementin, osioi elementit pienempiin ja suurempiin kuin se, ja sitten rekursiivisesti lajittelee molemmat puolet. Keskimäärin O(n log n), pahin tapaus O(n²).
Osiointi sijoittaa pivotin sen lopulliseen lajiteltuun paikkaan; kaikki vasemmalla on pienempiä, kaikki oikealla on suurempia. Rekursio molemmilla puolilla.
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-osiointia käytetään käytännössä muistin säästämiseksi.)
| Tapaus | Aika | Syy |
|---|---|---|
| Paras/Keskimäärin | O(n log n) | tasapainotetut osiot |
| Pahin | O(n²) | jo lajiteltu huonolla pivotilla |
In-place quicksort käyttää O(log n) pintatilaa.
Ole tavallisesti nopein käytännössä välimuistin ystävällisyyden ja alhaisen kuormituksen vuoksi, ja se on in-place. Pahin tapaus O(n²) vältetään satunnaistetulla tai median-of-three-pivotilla. Se ei ole vakaa.
Quicksort on oletuksena monissa vakiokirjastoissa sen erinomaisen keskimääräisen nopeuden ja alhaisen muistin käytön vuoksi.
Ymmärtäminen siitä, miksi pivot-valinta aiheuttaa pahimman tapauksen O(n²), opettaa tärkeän opetuksen: keskimääräinen ja pahin tapaus voivat erota jyrkästi.
Se on suosittu haastatteluaihe juuri tämän vivahteen vuoksi.