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

Vnútorné triedenie

Vnútorný triedenie je akýkoľvek triediaci proces, ktorý prebieha v hlavnej pamäti počítača. To je možné ak údaje, ktoré majú byť triedené majú takú veľkosť, že sa dokážu nahrať do hlavnej pamäti. Akékoľvek čítanie alebo zápis dát do/z externej pamäte môže značne spomaliť proces triedenia.

Uvažujem algoritmus Bubblesort, kde sa vymieňajú priľahlé záznamy s cieľom dostať ich do správneho poradia. V prípade, že časť triedeného súboru by bola b hlavnej pamäti a časť na externej pamäti, neustále by sa musel nahrávať do pamäti ten blok spboru, v ktorom sa vykonáva "prebulávanie".

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)[/math]	---	[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 triedenia

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.

Princíp známych triediacich algoritmov

Bubble sort

Bubble sort predstavuje jednoduchý spôsob triedenia dát. Algoritmus začína na začiatku súboru údajov. Porovnáva prvé dva prvky, a ak je prvý väčší ako druhý, tak ich zamení. Toto robí pre každú dvojicu susedných prvkov až po koniec dátového súboru. Potom začína odznova s prvými dvoma prvkami, až pokiaľ nie je čo zameniť. Tento algoritmus je veľmi neefektívny, a málo použiteľný. Napríklad, ak budeme mať utriediť 100 prvkov, potom celkový počet porovnaní bude 10 000. Mierne lepšia varianta je Shake sort (Coctail sort), ktorý pracuje na princípe Buublesort ale prebublávanie sa deje striedavo smerom zľava doprava (a opačne). Modifikovaný Bubblesort zmenšuje počet porovnaní na 4950 (pri 100 prvkoch)

Selection sort

Princíp fungovania je, že sa vyberie z nezotriedenej časti postupnosti prvok s minimálnou hodnotou a vloží sa na koniec zotriedenej časti postupnosti. Na začiatku má zotriedená postupnosť 0 prvkov a nezotriedená má toľko prvokv, koľko je veľkosť poľa.

Shell sort

Pracuje podobne ako Selectionsort na princípe výberu. Shellsort vylepšuje vkladanie prvkov zadefinovaním kroku pri porovnávaní prvkov. Viacnásobným prechodom triedeným poľom a zmenšovaním kroku dosahuje lepšie výsledku ako InsertSort. Tento algoritmus je vhodné na zoznamy, ktoré sú skoro utriedené.

Merge sort

Merge sort využíva spájanie už zotriedených zoznamov do nového zoznamu, ktorý bude tiež zotriedený. Začína porovnávaním každých dvoch prvkov (tj 1 s 2,potom s 3, potom s 4, ...) a ich vzájomnou zámenou, aby boli zotriedené. Potom sa spojí každý z výsledných zoznamov (zatiaľ dvojprvkových) na štvrprvkový zoznam, a tak ďalej, až pokiaľ nie sú posledné dva zoznamy zlúčené do finálneho usporiadaného zoznamu.

Heap sort

Heapsort je efektívnejšia verzia Selectionsort-u. Funguje na výbere najmenšieho/najväčšieho prvku a umiestnením na začiatok/koniec zoznamu. Podobným spôsobom sa pokračuje zo zvyškom zoznamu. Pracuje sa s dátovou štruktúrou halda, čo je špeciálny prípad binárneho stromu.

Quick sort

Quicksort je algoritmus typu "rozdeľuj a panuj". Funguje na princípe rozdelenia triedeného poľa vzhľadom na vzťažný prvok (pivot) tak že prvky menšie ako pivot sú naľavo od pivota a prvky väčšie ako pivot sú napravo od pivota. Potom sa algoritmus rekurzívne aplikuje na tieto rozdelenia.

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.