Quicksort yra dalyk-ir-nugalėk rūšiavimas, kuris pasirenka šarnyrą, padalija elementus į mažesnius ir didesnius nei jis, tada rekursyviai rūšiuoja abi puses. Vidutinis O(n log n), blogiausias atvejis O(n²).
Dalijimas nustato šarnyrą jo galutinėje rūšiavimo padėtyje; viskas kairėje yra mažiau, viskas dešinėje yra daugiau. Rekursiniu būdu abiem pusėm.
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]
(Vietos padalijimas praktikoje naudojamas atminčiai taupyti.)
| Atvejis | Laikas | Priežastis |
|---|---|---|
| Geriausias/Vidutinis | O(n log n) | subalansuoti skaidymai |
| Blogiausias | O(n²) | jau surūšiuotas su bloga šarnyru |
Vietos greitasis rūšiavimas naudoja O(log n) dėmės erdvę.
Paprastai greitausias praktikoje dėl keš draugiškumo ir žemos sąnaudos, ir jis yra vietos. Blogiausias atvejis O(n²) išvengiamas atsitiktiniu arba trijų medianų šarnyru. Jis nėra stabilus.
Greitasis rūšiavimas yra numatytasis daugelyje standartinių bibliotekų dėl puikaus vidutinio atvejo greičio ir žemos atminties sąnaudos.
Supratimas, kodėl šarnyro pasirinkimas sukelia O(n²) blogiausią atvejį, moko svarbią pamoką: vidutinis ir blogiausias atvejai gali drastiškai skirtis.
Tai yra mėgstama apklausa tiksliai dėl tos subtilybės.