Quicksort je algoritmus řazení typu divide-and-conquer, který si zvolí pivot, rozdělí prvky na ty menší a větší než on, a pak rekurzivně řadí obě strany. Průměr O(n log n), nejhorší případ O(n²).
Dělení umístí pivot na jeho konečnou pozici v seřazeném poli; vše vlevo je menší, vše vpravo je větší. Rekurzivně zavolej na obě strany.
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]
(Dělení na místě (in-place) se v praxi používá k úspoře paměti.)
| Případ | Čas | Důvod |
|---|---|---|
| Nejlepší/průměr | O(n log n) | vyvážená dělení |
| Nejhorší | O(n²) | již seřazeno se špatným pivotem |
Quicksort na místě používá O(log n) místa na stacku.
Za normálních okolností nejrychlejší v praxi díky cache-friendly přístupu a nízkým režijním nákladům a je to in-place algoritmus. Nejhorší případ O(n²) se vyhneme randomizovaným nebo median-of-three pivotem. Není stabilní.
Quicksort je výchozí v mnoha standardních knihovnách kvůli jeho vynikajícímu průměrnému výkonu a nízké spotřebě paměti.
Pochopení toho, proč volba pivotu vede k nejhoršímu případu O(n²), učí důležitou lekci: průměr a nejhorší případ se mohou výrazně lišit.
Je to oblíbené téma při pohovorech právě kvůli této nuanci.