Triediaci algoritmus

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie
Selection-Sort-Animation.gif

Triedaci 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[upraviť | upraviť zdroj]

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(n2). 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[upraviť | upraviť zdroj]

Iné projekty[upraviť | upraviť zdroj]