Quicksort

Z Wikipédie

Quicksort alebo rýchle triedenie je jeden z najrýchlejších známych triediacich algoritmov, založených na porovnávaní prvkov. Jeho priemerná doba výpočtu je najlepšia zo všetkých podobných algoritmov (O(n.log(n))). Algoritmus je aj veľmi jednoduchý. Nevýhodou je, že pri výnimočne nevhodnom tvare vstupných dát môže byť časová a pamäťová náročnosť tohto algoritmu až O(n²).

[úprava] Algoritmus

Základnou myšlienkou quicksortu je rozdelenie triedenej postupnosti čísel na dve približne rovnaké časti. V jednej časti sú čísla väčšie a v druhej menšie ako istá zvolená hodnota, ktorá sa nazýva pivot. Ak je táto hodnota zvolená dobre, sú obe časti približne rovnako veľké. Ak budú obe časti samostatne roztriedené, je roztriedené i celé pole. Obe časti sa potom rekurzívne triedia rovnakým spôsobom.

Najväčším problémom celého algoritmu je voľba pivotu. Ak sa podarí zvoliť číslo blízke mediánu triedenej časti poľa, je algoritmus najrýchlejší. Ak nie, je jeho pamäťová a časová náročnosť vyššia, ako pri všetkých ostatných algoritmov.