GMLWiki

Tato stránka je pouze pro čtení. Můžete si pouze prohlédnout zdrojový kód, ale ne ho měnit. Zeptejte se správce, pokud si myslíte, že něco není v pořádku.
====== 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<sup>2</sup>) 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<sup>2</sup>)

**Ukázka algoritmu:**
<code javascript>
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;
            }
        }
    }
}
</code>
<html>

<script>
function test() {
    var x = [2, 5, 1, 7, 8];

    bubbleSort(x);
}

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

}

function printStep(array, step) {
    var container = document.getElementById("containerbubble");
    container.innerHTML += "Krok " + step + ": "
    for (var index = 0; index < array.length; index++) {
        container.innerHTML += array[index] + " ";
    }
    container.innerHTML += "<br />";
}

</script> 
    <div id="containerbubble">
    </div>
    <script src="bubblesort.js"></script>

    <button onclick="test()">Spusť mě!</button>

</html>

==== 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<sup>2</sup>), ale při téměř seřazeném poli se blíží O(n).

**Ukázka algoritmu:**

<code javascript>
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;
       }
    }
}


</code>
 
<html>
<script>
function testInsert() {

    var x = [1, 5, 6, 7, 8];

    insertSort(x);

}


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]) {
            printStepIns(array, stepCounter++);

            array[j] = array[j - 1];
            j--;
            array[j] = tmp;
       }
    }
    printStepIns(array, stepCounter++);
}

function printStepIns(array, step) {
    var container = document.getElementById("containerinsert");
    container.innerHTML += "Krok " + step + ": "
    for (var index = 0; index < array.length; index++) {
        container.innerHTML += array[index] + " ";
    }
    container.innerHTML += "<br />";
}

</script>
    <div id="containerinsert">
    </div>
    <button onclick="testInsert()">Test me!</button>
</html>

==== 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<sup>2</sup>). 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<sup>2</sup>), 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<sub>2</sub>(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.