Quicksort
Vybere jednu hodnotu, tzv. pivot, a menší hodnoty přesune nalevo od něj, větší napravo. Pak totéž udělá s každou stranou.
- Ω(n log n)
- Θ(n log n)
- O(n²)
- O(log n)
- ne
- ano
Nejlepší případ: jak roste čas s velikostí seznamu n, když je vstup pro tento algoritmus nejsnazší.
Průměrný: obvyklý růst času s n. Při n² trvá dvakrát víc hodnot asi čtyřikrát déle; n log n roste mnohem pomaleji.
Nejhorší: růst času na nejtěžším vstupu. Důležitý, když se řazení nesmí nikdy zpomalit.
Paměť: kolik paměti navíc je potřeba kromě seznamu. 1 znamená pár proměnných, n kopii seznamu.
Stabilní: dvě stejné hodnoty si zachovají původní pořadí. Důležité při řazení záznamů podle jednoho pole.
Bez paměti navíc: řadí přímo uvnitř seznamu, bez druhého seznamu.
- porovnávání
- přesun
- pivot
- na konečném místě
Hloubka rekurze: 0 · nejmenší možná: 4 · nejhorší: 23 čeká na svůj pivot
Stiskněte Přehrát: čáry ukazují, jak během řazení rostou náklady
Stiskněte Přehrát nebo procházejte algoritmus krok po kroku.
Mezerník: přehrát nebo pozastavit. Šipky vlevo/vpravo: krok. Home a End: přeskočit.
Zkuste: Zvolte obrácený seznam. Pivot je vždy nejmenší nebo největší ze zbylých hodnot, takže jedna strana je prázdná a náklady rostou k n².
Jak to funguje
Pivotem je tu poslední hodnota úseku. Zleva doprava se každá hodnota, která není větší než pivot, prohodí na levou stranu. Pak se pivot postaví mezi obě strany a tam už zůstane. Každá strana se nakonec seřadí stejně.
Kdy se hodí
V praxi jeden z nejrychlejších způsobů řazení a skoro nepotřebuje paměť navíc. Když ale opakovaně vybírá špatný pivot, třeba na už seřazeném seznamu, zpomalí se. Proto se v praxi pivot vybírá pečlivěji.