Triedenie

Pojmom triedenie sa v informatike myslí zoradzovanie prvkov podľa nejakej vlastnosti. Teda napríklad zoradenie čísel od najmenšieho po najväčšie, zoradenie reťazcov (slov) podľa abecedy atď..

Vstupom triediacich algoritmov je teda nejaká postupnosť prvkov, väčšinou už načítaná v nejakom poli (alebo inej dátovej štruktúre), výstupom má byť postupnosť tých istých prvkov, správne usporiadaná.

Existuje veľa známych algoritmov na triedenie, tu spomenieme iba niekoľko najznámejších.

Triediace algoritmy založené na porovnávaní

Tieto algoritmy o prvkoch, ktoré chceme triediť, predpokladajú iba to, že ich vieme porovnávať. To znamená, že sa vieme pozrieť na dva prvky a rýchlo povedať, ktorý z nich má ísť vo výslednom poradí skôr. Ich výhodou je ich univerzálnosť: Chcete zoradiť čísla podľa veľkosti? Stačí ak pre každé dve čísla viete povedať, ktoré je menšie. Chcete zoradiť slová podľa abecedy? Stačí vedieť povedať, ktoré slovo je v abecede skôr. Chcete zoradiť zajace podľa ružovosti? Stačí ak viete povedať, ktorý zajac je ružovejší.

Časové zložitosti uvedené v nasledujúcej tabuľke sú za predpokladu, že dva prvky vieme porovnať v konštantnom čase. Dá sa dokázať, že triedenie založené len na porovnávaní nemôže mať priemernú časovú zložitosť lepšiu ako $O(n \log n)$.

Z uvedených algoritmov si v tejto Kuchárke môžete prečítať o nasledujúcich:

• Mergesort

• Heapsort - ak všetky prvky vložíte do minimovej haldy a následne ich postupne všetky vyberiete do poľa, úspešne ste vykonali (asymptoticky) optimálne triedenie.

Iné triediace algoritmy

Tieto algoritmy o triedených prvkoch predpokladajú nejaké veci navyše. Vďaka tomu môžu mať lepšiu časovú zložitosť než $O(n \log n)$, nedajú sa však použiť vždy.

• Count sort predpokladá, že triedime čísla z nejakého malého rozsahu.
• Radix sort sa dá použiť, keď lexikograficky triedime postupnosti prvkov z nejakej malej množiny (napríklad postupnosti písmen (reťazce), postupnosti cifier (čísla), ...).