====== Třídění/Řazení a vyhledávací algoritmy ====== ===== Třídění vs. řazení ===== Třídění je uspořádání objektů podle podobných vlastností. Způsob třídění je vždy závislý na oboru, který s těmito objekty pracuje. Řazení je způsob uspořádání objektů do specifikovaného pořadí. Řazení může být provozováno podle různých kritérií (abecedně, vzestupně, sestupně). Oba pojmy bývají často zaměňovány. ===== Složitost algoritmů ===== Složitost algoritmů (někdy taky asymptotická složitost) je funkce, která vyjadřuje počet elementárních kroků v závislosti na vstupních datech dané funkce. Značí se O. Možnosti tříd složitostí: {{:informatika:maturita:22_slozitost_algoritmu.png|}} Rozdíl mezi jednotlivými třídami složitosti se dá jednoduše pochopit na těchto dvou příkladech. Když máme první algoritmus se složitostí O(n) a druhý algoritmus se složitostí O(2n) stačí nám ten druhý spustit na dvakrát rychlejším stroji a rozdíl je smazán. Pokud však máme první algoritmus se složitostí O(n) a algoritmus se složitostí O(n²) bude při různé velikosti stoupat náročnost v závislosti na n, a to několikrát. ===== Řadicí algoritmy ===== ==== Bubble sort ==== **Princip:** - Dostanu pole. - Procházím pole, pokud najdu prvek, který je menší než prvek vpravo, prohodím je. - Opakuji, dokud není pole seřazeno od největšího po nejmenší (zprava doleva). **Složitost:** O(n²) **Ukázka algoritmu:**


function bubbleSort(array) {
    for (var i = 0; i < array.length - 1; i++) {
        for (var j = 0; j < array.length - 1 - i; j++) {
            if (array[j] < array[j + 1]) {
                var tmp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = tmp;
            }
        }
    }
}

==== Insert sort ==== **Princip:** - Dostanu pole. - Procházím pole zleva doprava a vždy každý prvek zařadím na místo podle jeho velikosti. - Dostávám pole seřazené zleva doprava (od největšího po nejmenší). **Složitost:** Složitost je O(n²), ale při téměř seřazeném poli se blíží O(n). **Ukázka algoritmu:**


function insertSort(array) {
    var stepCounter = 0;
    for (var i = 0; i < array.length - 1; i++) {
        var j = i + 1;
        var tmp = array[j];
        while (j > 0 && tmp > array[j - 1]) {
            array[j] = array[j - 1];
            j--;
            array[j] = tmp;
       }
    }
}

==== Merge sort ==== https://www.algoritmy.net/article/13/Merge-sort **Princip:** - Dostaneme pole. - Pole rozdělíme na dvě zhruba stejně velká podpole. - Získané podpole dále dělíme až na jednoprvkové pole (získáme n jednoprvkových polí). - Jakmile máme jednoprvková pole spojujeme je dohromady tak, aby byly seřazeny. - Jakmile máme jenom dvě podmnožiny, porovnáme vždy jednotlivé prvky množiny a vždy ten větší přidáme do finálního pole -> postupujeme až máme ve finálním poli prvky od největšího po nejmenší. **Složitost:** O(n * log(n)) Ukázka [[https://www.youtube.com/watch?v=EeQ8pwjQxTM|zde]]. ==== Quick sort ==== **Princip:** - Dostaneme pole. - Zvolíme si jeden prvek pole (pivot) a rozdělíme zbytek pole na prvky větší než pivot a na prvky menší než pivot (stejně velké prvky mohou být na libovolné straně). - Pivota umístíme mezi tyto dvě množiny (pivot je na místě, kam by patřil v seřazeném poli). - Kroky opakujeme, dokud nemáme všechny prvky seřazeny. **Složitost:** Složitost u quick sortu je hodně závislá na volbě pivota (resp. pivotů). Pokud je pivot mediánem hodnot, může být složitost až O(n * log(n)), pokud je však pivot největším nebo nejmenším prvkem pole je složitost O(n²). Pivota můžeme vybrat jako fixní pozici v tabulce (např. vždy poslední, první nebo prostřední prvek) nebo, což se považuje za ideální případ, se vyberou tři hodnoty pole, ze kterých se udělá medián. Ukázka [[http://www.algoritmy.net/article/10/Quicksort|zde]]. ==== Selection sort ==== **Princip:** - Dostaneme pole. - Vyhledáme největší prvek pole a umístíme ho doleva. - Toto opakujeme, dokud nemáme seřazeno. **Složitost:** Složitost je sice u selection sortu vysoká O(n²), ale má velmi nízkou paměťovou náročnost. [[http://www.algoritmy.net/article/4/Selection-sort|Ukázka algoritmu]] ===== Vyhledávací algoritmy ===== ==== Lineární hledání (sekvenční hledání) ==== **Princip:** Procházíme všechny prvky, dokud nenajdu ten hledaný. **Složitost:** O(n) ==== Binární hledání (metoda půlení intervalů) ==== **Princip:** - Pole ve kterém se dá použít půlení intervalů, musí být seřazeno (v tomto případě od největšího po nejmenší). - Podívám se na prostřední prvek pole. - Pokud je můj hledaný prvek větší opakuji to stejné vpravo, pokud menší tak vlevo. - Opakuji, dokud nenajdu hledaný prvek. **Složitost:** O(log₂(n)) ==== Metoda binárního vyhledávacího stromu ==== **Princip:** Tvořím binární strom (viz obrázek) tak, že vždy v levé větvi jsou menší prvky a v pravé jsou větší prvky. Hledaný prvek hledáme tak, že za ním jdeme po větvi. {{:informatika:maturita:22_binarni_strom.jpg|}} **Složitost:** V závislosti na vyvážení stromu (podle vyváženého počtu větví na obou stranách) může být buď O(log(n)) pro naprosto vyvážený strom, nebo až O(n) pro vůbec nevyvážený strom.