Algoritmy triedenia

Algoritmy a programovanie

---

Dátový typ

Štruktúry

Rekurzia

Algoritmy vyhľadávania

Algoritmy triedenia
 ::Triedenie výmenou
 ::Triedenie vkladaním
 ::Triedenie zlučovaním
 ::Triedenie delením
 ::Triedenie výberom
 ::Triedenie - ostatné princípy

Lineárny zoznam

Binárny strom

Numerické algoritmy

Grafové algoritmy

Triedenie

Triedaci algoritmus je v informatike algoritmus, ktorý zoraďuje prvky zoznamu v určenom poradí. Najpoužívanejšie sú numerické a lexikografické poradie. Efektívne triedenie je dôležité pre optimalizáciu použitia iných algoritmov (ako je napr. vyhľadávanie), ktoré vyžadujú pre svoju správnu funkčnosť utriedené zoznamy. Formálne povedané, výstupné utriedené údaje musia spĺňať dve podmienky:

1. Prvky vo výstupnom zozname majú neklesajúci trend (každý prvok je väčší alebo rovný ako predchádzajúci prvok)
2. Výstupom je permutácia vstupných resp. preusporiadanie týchto údajov.

Klasifikácia

Triediace algoritmy môžeme klasifikovať podľa:

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í.

Využitie pamäte

(a využívanie ďalších počítačových zdrojov). Niektoré triediace algoritmy sú typu "in-place". To znamená, že im stačí O(1) alebo O(log n) pamäte na triedené položky.

Rekurzia

Niektoré algoritmy sú buď rekurzívne alebo nerekurzívne, niektoré môžu byť implementovateľné oboma spôsobmi (napr. Merge sort).

Stabilita

Stabilné triediace algoritmy - súvis s triedením dvojíc kľúč-hodnota, pričom existujú 2 také záznamy, že kľúče sú rovnaké. Stabilný algoritmus nezmení poradie týchto dvojíc vo výsledku.

Metóda triedenia

vkladanie, výmena, výber, zlúčenie, a pod.

Porovnanie algoritmov

V nasledujúcej tabuľke je n počet záznamov, ktoré majú byť utriedené. Stĺpce "Priemerne" a "najhoršie" hovoria o časovej zložitosti, za predpokladu, že dĺžka všetkých kľúčov je konštantná, a preto všetky porovnania, výmeny a ďalšie potrebné operácie môže vykonať v konštantnom čase. "Pamäť" označuje množstvo pomocnej potrebnej okrem tej, ktorá je potrebná na samotné uloženie poľa ktoré sa bude triediť.

table name

Názov	Priemerne	Najhoršie	Pamäť	Metóda tiedenia
Bubble sort	[math]n^2[/math]	[math]n^2[/math]	1	Výmena
Gnome sort	---	[math]n^2[/math]	1	Výmena
Shake sort	---	[math]n^2[/math]	1	Výmena
Selection sort	[math]n^2[/math]	[math]n^2[/math]	1	Výber
Shell sort	---	[math]n \cdot \log^2 n[/math]	1	Vkladanie
Merge sort	[math]n \cdot \log n[/math]	[math]n \cdot \log n[/math]	n	Zlučovanie
Heap sort	[math]n \cdot \log n[/math]	[math]n \cdot \log n[/math]	1	Výber
Quick sort	[math]\mathcal{O}(n \cdot \log n)[/math]	[math]\mathcal{O}(n^2)[/math]	[math]\mathcal{O}\log n[/math]	Delenie