Quicksort
Quicksort je třídicí algoritmus, který se používá k třídění prvků v poli. Vytvořil ho Tony Hoare v roce 1959 a dodnes se hojně používá. Quicksort vytváří v poli oddíly, což v podstatě znamená, že rozdělí pole na dvě části a pak pokračuje v rozdělování těchto částí na další části a třídění po cestě. Vlastní třídění provádí díky tomu, že se jedná o porovnávací třídění. To znamená, že vybere v poli otočný bod a pak jej porovná se všemi ostatními body v poli.
Animovaná vizualizace algoritmu quicksort. Vodorovné čáry jsou hodnoty pivotů
Algoritmus
- Vyberte libovolný prvek v poli, který bude nyní otočným bodem.
- Rozdělení prvků. Porovnejte všechny prvky v poli s pivotem, prvky, které jsou nižší než pivot, přesuňte vlevo od pivotu a všechny prvky v poli, které jsou vyšší než pivot, přesuňte vpravo od pivotu. Všimněte si, že náš pivot je nyní v setříděné pozici.
- Projděte znovu do obou oddílů. Použijte výše uvedené dva kroky na dva oddíly, které jsme vytvořili v kroku 2.
Jako pivot se často volí nejlevější prvek. Rekurze znamená, že algoritmus provede přesně stejný algoritmus na dvou oddílech, které byly vytvořeny porovnáním s pivotem. Všimněte si, že tento algoritmus bude pokračovat v rozdělování pole na podpole a rozdělování těchto podpolí na ještě menší podpole. Pokaždé, když to udělá, vybere nový pivot v rámci podpole a porovná prvky s tímto podpolem. Základním případem je situace, kdy algoritmus dospěje k podmřížce s jediným prvkem, v níž se prostě zastaví, protože jeden prvek není třeba třídit.
