Triediaci algoritmus

Z Wikipédie

Na tomto článku sa práve pracuje.
Pokiaľ je tu zobrazená táto správa, prosím neupravujte tento článok. Vyhnete sa tak prípadným konfliktom pri upravovaní článku. Redaktor, ktorý sem pridal tento oznam, je uvedený v histórii, ak by ste ho chceli kontaktovať.

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.

[úprava] 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(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í.