Porovnání řadicích algoritmů

Ř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ámka	Přirozený	Stabilní	Složitost
Bubble sort		ano	ano	$O(n^{2})$
Shakersort		ano	ano	$Ο(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)$

Časová složitost

Stabilita řazení

Přirozenost algoritmu

Srovnání

Doporučujeme