Vstup: Číslo $n$ a posloupnost čísel $A = a_1, a_2, \dots , a_n$.
Výstup: Taková permutace $A' = a'_1 , a'_2 , \dots , a'_n$ vstupní posloupnosti $A$, že platí $a' 1 \leq a'_2 \leq \dots ≤ a'_n$.
Například:
$n = 6, A = 23, 7, 19, 21, 5, 12, A' = 5, 7, 12, 19, 21, 23$.
Obecně: ze vstupní posloupnosti vytvořit posloupnost hodnot v předdefinovaném pořadí.
Existuje řada přístupů a algoritmů.
Fundamentální problém v informatice.
Implicitně budeme uvažovat algoritmy řadicí vzestupně.
Základní operace:
Řazení založené na pouze binární operaci porovnání-a-prohození (Compare-And-Exchange).
Řazení založené na jiné operaci.
Paměťová náročnost:
In-place algoritmy (potřebují $n + \text{polylog}(n)$ paměti).
Out-of-place algoritmy.
Stabilita
Stabilní algoritmy (stejně velké prvky se nikdy neprohodí).
Nestabilní algoritmy (stejně velké prvky se mohou prohodit).
Citlivost na hodnoty prvků vstupní posloupnosti:
Datově citlivé algoritmy (časová složitost závisí na hodnotách prvků)
Datově necitlivé algoritmy (časová složitost nezávisí na hodnotách prvků).