Řadící algoritmy slouží k setřízení jednotlivých prvků vstupního souboru (obvykle seznamu) dle jejich velikosti. Při volbě vhodného řadícího algoritmu je třeba dbát na několik kritérií - výkon algoritmu (jeho časová složitost), implementační složitost, vhodnost pro danou datovou strukturu a v neposlední řadě stabilita algoritmu.

Časová složitost

Z hlediska časové složitosti jsou nejvýkonnějšími algoritmy ty, které neporovnávají jednotlivé hodnoty prvků, ale fungují na jiném pricipu (složitost O(n)). Příkladem je například counting sort (který počítá výskyty jednotlivých hodnot) nebo radix sort (řadí řetězce fixní délky dle jednotlivých znaků). Tyto algoritmy ale nejsou vhodné pro všeobecné použití.

Z tohoto důvodu volíme algoritmy třídy Ο(n \\cdot \\log(n))heapsort, quicksort nebo merge sort. Tyto algoritmy jsou optimální, jelikož bylo dokázáno, že algoritmus založený na bázi porovnávání hodnot musí mít složitost \\Theta (n \\cdot \\log(n)).

Za předpokladu malé velikosti dat jsou vhodným řešením algoritmy se složitostí Ο(n^{2})bubble sort, insertion sort, selection sort, protože je jejich implementace velmi jednoduchá. Z kvadratických algoritmů je nejvýkonnější Shell sort - řazení se snižujícím se přírůstkem.

Stabilita řazení

Říkáme, že je řazení stabilní, pokud nedojde v jeho průběhu k prohození prvků se stejnou hodnotou. Tato vlastnost je užitečná, jestliže dochází k postupnému řazení podle dvou (a více) parametrů. Řadíme-li například žáky v třídní knize napřed dle křestního jména a poté dle příjmení, pak výsledek stabilního algoritmu odpovídá očekávání (první je Karel Novák, následuje Václav Novák). Pokud by algoritmus nebyl stabilní, tak tento postup nebude fungovat, protože druhé řazení by mohlo zpřeházet výsledek prvního (Václav Novák by mohl být před Karlem Novákem).

Přirozenost algoritmu

Další vlastností řadících algoritmů je jejich přirozenost. Přirozený algoritmus rychleji zpracuje již částečně seřazenou posloupnost, zatímco u algoritmu, který přirozený není, tento fakt nehraje žádnou roli.

Srovnání

Název PoznámkaPřirozený Stabilní Složitost
Bubble sort ano ano O(n^{2})
ShakersortanoanoΟ(n^{2})
Selection sort ne ne \\Theta (n^{2})
Insertion sort ano ano Ο(n^{2})
Shell sort Nejvýkonnější kvadratický algoritmus ano ne Ο(n^{2})
Heapsort ne ne \\Theta(n \\cdot \\log(n))
Merge sort ano ano \\Theta(n \\cdot \\log(n))
Quicksort Očekávaná složitost - při špatné volbě pivota až Ο(n^{2}) ne ne O(n \\cdot \\log(n))
Radix sort Konstantní délka řazených řetězců ne ano \\Theta(n)
Counting sort Má smysl počítat výskyty hodnot ne ano \\Theta(n)







Doporučujeme