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ů (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.
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(n2) bude při různé velikosti stoupat náročnost v závislosti na n, a to několikrát.
Princip:
Složitost: O(n2)
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:
Složitost: Složitost je O(n2), 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; } } }
https://www.algoritmy.net/article/13/Merge-sort
Princip:
Složitost: O(n * log(n))
Ukázka zde.
Princip:
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(n2). 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 zde.
Princip:
Složitost: Složitost je sice u selection sortu vysoká O(n2), ale má velmi nízkou paměťovou náročnost.
Princip: Procházíme všechny prvky, dokud nenajdu ten hledaný.
Složitost: O(n)
Princip:
Složitost: O(log2(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 (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.