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ě).

Tyto dva pojmy bývají často zaměňovány.

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

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 10x, 20x,…

Princip:

1. Dostanu zadané pole.
2. Procházím pole, pokud je prvek vlevo menší než prvek vpravo prohodím je
3. Opakuji dokud není pole seřazeno od největšího po nejmenší (zprava doleva)

Složitost: O(n²) → za každý prvek pole projdu pole dvakrát

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

Princip:

1. Dostanu pole
2. Procházím pole zleva doprava a vždy každý prvek zařadím na místo podle velikosti
3. 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;
       }
    }
}

Princip:

1. Dostaneme pole
2. Toto pole si rozdělíme na dvě podpole
3. Dokud není pole rozděleno na jednoprvkové pole opakuj krok č.2
4. Jakmile máme jednoprvková pole spojíme je dohromady tak, aby byly seřazeny
5. 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: Složitost algoritmu O(n * log(n))

Protože to nejsem schopný naprogramovat ukázku máte zde .

Princip:

1. Dostaneme pole
2. 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
3. Pivota umístíme mezi tyto dvě množiny → pivot je na místě, kam by patřil v seřazeném poli
4. 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 O(n * log(n)), pokud však je 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í nebo první nebo prostřední prvek) nebo, což se považuje za idealnější případ, se vyberou tři hodnoty a z nich se udělá medián.

Protože to nejsem schopný naprogramovat ukázku máte zde .

Princip:

1. Dostaneme pole
2. Vyhledáme největší prvek pole a umístíme ho doleva
3. Toto opakujeme, dokud nemáme seřazeno

Složitost: Složitost je sice u selection sortu vysoká O(n²), ale dobrá je u něj jeho nízká paměťová náročnost

Ukázka algoritmu

Princip: Procházím všechny prvky, dokud nenajdu ten hledaný.

Složitost: O(n)

Princip:

1. 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ší)
2. Podívám se na prostřední prvek pole
3. Pokud je můj hledaný prvek větší opakuji to stejné vpravo, pokud menší tak vlevo
4. Opakuji dokud nenajdu hledané číslo

Složitost: O(log₂(n))

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.

Složitost: V závislosti na vyvážení stromu (= vyvážený počet větví obou stranách) může být buď O(log(n)) pro vyážený strom nebo O(n) pro nevyvážený.