Obsah:
Definícia - Čo znamená Quicksort?
Quicksort je populárny triediaci algoritmus, ktorý je v praxi často rýchlejší v porovnaní s inými triediacimi algoritmami. Využíva stratégiu rozdelenia a dobývania na rýchle zoradenie dátových položiek rozdelením veľkého poľa na dve menšie polia. Bol vyvinutý Charlesom Antonym Richardom Hoare (bežne známym ako CAR Hoare alebo Tony Hoare) v roku 1960 pre projekt strojového prekladu pre Národné fyzikálne laboratórium.Techopedia vysvetľuje Quicksort
Quicksort je algoritmus používaný na rýchle zoradenie položiek v poli bez ohľadu na to, aké veľké je pole. Je pomerne škálovateľný a funguje relatívne dobre pre malé a veľké súbory údajov a je ľahké ho implementovať s malou časovou náročnosťou. Uskutočňuje to pomocou metódy rozdelenia a dobývania, ktorá rozdeľuje jedno veľké pole na dve menšie a potom tento proces opakuje pre všetky vytvorené polia, kým nie je zoradenie dokončené.
Algoritmus quicksort sa vykonáva takto:
- Otočný bod je vybraný zo súboru.
- Pole je usporiadané tak, že všetky hodnoty menšie ako pivot sa presunú pred ním a všetky hodnoty väčšie ako pivot sa posunú za ním, pričom hodnoty sa rovnajú pivotu v oboch smeroch. Keď sa tak stane, čap je vo svojej konečnej polohe.
- Vyššie uvedený krok sa opakuje pre každú podrámec menších hodnôt, ako aj pre podrámec s vyššími hodnotami.
Toto sa opakuje, až kým sa nezoradí celé pole.
