Řadicí (aka třídicí) algoritmy jsou algoritmy, jejichž vstupem je kolekce objektů (např. pole), které lze porovnat, tj. říci, který ze dvou objektů je větší, nebo menší, případně zda jsou (pro dané porovnávací kritérium) stejné.
Výstupem třídicího algoritmu je tatáž kolekce objektů, jejich pořadí je ovšem takové, že např. pro třídění od nejmenšího prvku po největší platí pro každé dva sousední prvky, že prvek s menším indexem je menší nebo roven prvku s větším indexem.
Třídění se hodí pro spoustu životních situací. Stále něco třídíme:
U třídicích algoritmů se sleduje jejich efektivita. Odborně se jedná o tzv. složitost, která vyjadřuje počet základních operací nutných k doběhnutí algoritmu.
Základními operacemi u třídění jsou zejména operace porovnání (comparison) dvou prvků v kolekci, kterou třídíme, a prohození (swap) dvou prvků v kolekci (změna jejich pozic, tedy vlastně indexů).
Například algoritmus Bubble sort, který má složitost O(n2), potřebuje pro setřídění vstupní kolekce o n prvcích n2 operací porovnání a prohození, kde n2 maximálně ještě vynásobíme nějakou konstantou, zde třeba třemi. (Tři operace na jedno prohození - např. porovnání, prohození, posuny indexů.) Máme-li tedy vstupní pole o 32 osobách, které chceme setřídit podle jejich roku narození, potřebujeme v Bubble sortu přibližně 32 x 32 x 3 = 1024 x 3 = 3072 operací pro úspěšné dokončení našeho záměru.
Použijeme-li Merge sort, který má složitost O(n log n), kde logaritmem se většinou míní logaritmus o základu 2, pak na setřídění stejné kolekce 32 osob podle roku narození budeme potřebovat např. pouze 32 x log 32 x 3 = 32 x 5 x 3 = 480 operací.
Kdyby provedení jedné základní operace trvalo přibližně 1 sekundu, trvalo by Bubble sortu setřídění kolekce 32 osob skoro hodinu, kdežto Merge sort by to zvládl asi za 8 minut.
Ukážeme si 3 příklady "pomalých" třídicích alogoritmů a 3 příklady efektivních třídicích algoritmů.
| Algoritmus | Princip | Složitost |
|---|---|---|
| Bubble sort | "Těžší" (větší) prvky probublávají na konec kolekce. | O(n2) |
| Insertion sort | V setříděné části kolekce vkládám postupně prvky na jejich "správné" místo. | O(n2) |
| Selection sort | Na konec setříděné části kolekce přidám vždy např. minimum z nesetříděné části. | O(n2) |
| Quicksort | Vyberu náhodně prvek z kolekce, tzv. pivot, a prvky menší než pivot dám vlevo, větší než pivot vpravo. Pak totéž provedu pro levou a pravou část, mezi nimiž je pivot. | O(n log n) |
| Merge sort | Rozdělím kolekci na mini-kolekce s jedním prvkem. Vezmu vždy dvě sousední jednoprvkové kolekce a spojím je do jedné, již setříděné. Pak vezmu výsledné dvouprvkové kolekce a spojuji vždy dvě a dvě stejným způsobem atd. | O(n log n) |
| Heapsort | Ze vstupní kolekce vyrobím haldu (heap), kde na dvou menších prvcích musí vždy "sedět" větší prvek. Zbytek je podobný Selection sortu, halda reprezentuje nesetříděnou část kolekce. | O(n log n) |