Obsah:
Definice - Co znamená Quicksort?
Quicksort je populární třídicí algoritmus, který je v praxi často rychlejší ve srovnání s jinými třídícími algoritmy. Využívá strategii rozdělení a dobytí k rychlému třídění datových položek rozdělením velkého pole do dvou menších polí. Byl vyvinut Charlesem Antonym Richardem Hoare (běžně známý jako CAR Hoare nebo Tony Hoare) v roce 1960 pro projekt strojového překladu pro Národní fyzikální laboratoř.Techopedia vysvětluje Quicksort
Quicksort je algoritmus používaný k rychlému třídění položek v rámci pole bez ohledu na to, jak velké pole je. Je poměrně škálovatelný a funguje relativně dobře pro malé i velké datové soubory a je snadno implementovatelný s malou časovou složitostí. Děje se to metodou rozdělení a dobytí, která rozdělí jediné velké pole na dvě menší a pak tento proces opakuje pro všechna vytvořená pole, dokud není řazení dokončeno.
Algoritmus quicksort se provádí takto:
- Otočný bod je vybrán z pole.
- Pole je uspořádáno tak, aby všechny hodnoty menší než pivot byly přesunuty před ním a všechny hodnoty větší než pivot byly přesunuty za ním, přičemž hodnoty rovnající se pivotu probíhaly v obou směrech. Po dokončení je otočný čep ve své konečné poloze.
- Výše uvedený krok se opakuje pro každou subarray o menších hodnotách a provádí se samostatně pro subarray s vyššími hodnotami.
Toto se opakuje, dokud není celé pole seřazeno.
