Triediaci algoritmus

Triediaci algoritmus je v informatike algoritmus, ktorý zoraďuje prvky zoznamu v určenom poradí. Najpoužívanejšie sú numerické a lexikografické poradie.

Efektívny triediaci algoritmus je dôležitý pre optimalizáciu iných algoritmov (ako vyhľadávacie a spájacie algoritmy), ktoré vyžadujú na správnu funkciu utriedený zoznam. Tiež sa používa na kanonizáciu údajov a tvorbu výstupu zrozumiteľného pre človeka. Formálne, výstup musí spĺňať dve podmienky:

1. výstup je vo neklesajúcom poradí (žiadny prvok nie je menší ako predchádzajúci prvok vzhľadom na požadované konečné poradie);
2. výstup je permutáciou (preusporiadaním) vstupu.

Od počiatkov informatiky priťahoval problém triedenia veľa záujmu výskumníkov, snáď vďaka zložitosti efektívneho riešenia napriek jednoduchému a intuitívnemu zadaniu. Napríklad bubble sort bol analyzovaný už v roku 1956 [1]. Hoci mnohí triedenie považujú za vyriešený problém, ešte aj dnes sa stále vyvíjajú užitočné nové triediace algoritmy (napríklad library sort bol prvýkrát publikovaný v roku 2004). Triediace algoritmy sú prevažne prezentované v úvodných kurzoch informatiky a programovania, kde hojnosť algoritmov riešiacich jeden problém poskutuje jemný úvod k rôznym fundamentálnym konceptom algoritmizácie ako notácia veľké O, algoritmy rozdeľ a panuj, údajové štruktúry, probabilistické algoritmy a analýza zložitosti.

Klasifikácia

Triediace algoritmy klasifikujeme podľa nasledovných kritérií:

• Výpočtová zložitosť (najhoršia, priemerná a najlepšia) pre zoznam s veľkosťou n položiek. Pre typické triediace algoritmy je prijateľná výpočtová zložitosť aspoň O(n.log n) a zlá O(n²). Ideálna zložitosť je O(n). Triediace algoritmy, ktoré používajú iba abstraktnú operáciu porovnania vždy majú priemernú zložitosť aspoň O(n.log n) porovnaní.

Druhy triediacich algoritmov

• Bogo sort
• Bubble sort
• Bucket sort
• Counting sort
• Heap sort
• Insertion sort
• Merge sort
• Quick sort
• Radix sort
• Selection sort
• Shaker sort
• Shell sort

Iné projekty

Commons

• Commons ponúka multimediálne súbory na tému Triediaci algoritmus