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.

Typy triediacich algoritmov

Vonkajšie triedenie

Vonkajšie triedenie je termín pre triedu triediacich algoritmov, ktoré môžu spracovať obrovské množstvo dát. Vonkajšie triedenie sa vyžaduje, ak sa triedené údaje nezmestia do hlavnej pamäte počítača (zvyčajne RAM) a namiesto toho musia byť umiestnené v pomalšej vonkajšej pamäti (zvyčajne pevný disk). Vonkajšie triedenie zvyčajne používa princíp zlučovania. Vo fáze triedenia sú dáta rozdelené do malých objemov ktoré sa zmestia do hlavnej pamäte. Pri fáze zlúčenia sú tieto bloky spojené do jedného väčšieho súboru.

Externý Mergesort

Príklad externého triedenia je algoristmus externého mergesortu.. Ako príklad uvádzame triedenie 900MB súboru ktorý rozdelíme na 100MB bloky, ktoré sú nahraté do pamäte.

1. Načítaj 100MB dát do hlavnej pamäti a utrieď ich ľubovoľným triediacim algoritmom.
2. Zapíš utriedený súbor na disk.
3. Opakuj kroky 1. a 2. pokiaľ nie sú utriedené všetky 100MB bloky dát. Potom budeme tieto bloky spájať.
4. Načítaj do pamäti prvých 10MB z každého utriedeného súboru. Alokuj zvyšných 10MB pre výstupný buffer.
5. Vykonaj 9-násobný algoritmus merge (spájanie) zapíš výsledok do výstupného bufferu. Ak je výstupný buffer zaplnený, zapíš tieto údaje do výsledného utriedeného súboru. Ak je ľubovoľný z 9-tich vstupných bufferov prázdny, naplň ho ďalšími 10MB z jeho 100MB utriedeného súboru.

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

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

Popis metód tiedenia

Existuje niekoľko základných druhov algoritmov univerzálneho vnútorného triedenia. Niektoré z pokročilejšách algoritmov využívajú viacero postupov.

Triedenie výberom

V súbore sa vždy nájde najmenší zo zostávajúcich položiek a uloží na koniec postupne vytváraného utriedeného súboru.

Triedenie vkladaním

Zo súboru neusporiadaných dát sa postupne berie položka po položke a vkladá sa na správne miesto v usporiadanom súbore (na začiatku je prázdny).

Triedenie výmenou

V súbore sa vždy nájde (nejakou metódou závislou na konkrétnom algoritme) nejaká dvojica prvkov, ktorá je v zlom poradí, a tieto prvky sa navzájom zamenia.

Triedenie zlučovaním

Vstupný súbor sa rozdelí na časti, ktoré sa (typicky rekurzívne) zoradia. Výsledné časti sa potom zlúčia takým spôsobom, aby aj výsledok bol zoradený.

Neexistuje žiaden "dokonalý" triediaci algoritmus, ktorý by bol ideálny pre všetky použitia. Rôzne algoritmy majú rôzne vlastnosti čo sa týka ich očakávané časovej a pamäťovej zložitosti, náročnosti implementácie a ďalších vlastností. Pre konkrétne podmienky sa tak často navrhujú špecifické varianty.

Odkazy

• Donald E. Knuth: The Art of Computer Programming, Volume 3: Sorting and Searching. Second Edition. Reading, Massachusetts: Addison-Wesley, 1998. ISBN 0-201-89685-0
• Algoritmy řazení ve slovníku algoritmů a datových struktur NIST
• Třídění ve výukových materiálech k předmětu Základy algoritmizace
• David R. Martin: Sorting Algorithm Animations - http://www.sorting-algorithms.com
• Algorithms in Java, Parts 1-4, 3rd edition by Robert Sedgewick. Addison Wesley, 2003.