A quicksort egy oszd meg és urald típusú rendezés, amely kiválaszt egy pivotot, particionálja az elemeket az ennél kisebbek és nagyobbak alapján, majd rekurzívan rendezi mindkét oldalt. Átlagos O(n log n), legrosszabb eset O(n²).
A particionálás a pivotot a végső rendezett helyzetébe helyezi; minden bal oldali elem kisebb, minden jobb oldali elem nagyobb. Rekurzívan mindkét oldalt feldolgozzuk.
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]
(A gyakorlatban helyben történő particionálást használunk a memória megtakarítása érdekében.)
| Eset | Idő | Ok |
|---|---|---|
| Legjobb/Átlagos | O(n log n) | kiegyensúlyozott partíciók |
| Legrosszabb | O(n²) | már rendezett sorrend rossz pivottal |
A helyben történő quicksort O(log n) veremtárat használ.
Gyakorlatban általában a leggyorsabb a cache-barátságossága és alacsony terhelése miatt, és helyben működik. Az O(n²) legrosszabb esetet elkerüljük egy randomizált vagy median-of-three pivot választásával. Nem stabil.
A quicksort az alapértelmezett sok szabványos könyvtárban az kiváló átlagos időbonyolultsága és alacsony memóriahasználata miatt.
A pivot választás által okozott O(n²) legrosszabb eset megértése egy fontos leckét tanít: az átlagos és legrosszabb eset élesen eltérhet egymástól.
Egy kedvelt interjúkérdés pontosan emiatt az árnyalatosság miatt.