Řadící algoritmy
Řazení podle určitého kritéria je velmi častý problém, který je nutné algoritmicky řešit. Odhaduje se, že řazením aplikace stráví až čtvrtinu času. Řazení se totiž objevuje jako častá podúloha v mnoha dalších algoritmech. Proto byl tento problém zkoumán a řešen mnoha významnými informatiky.
Bylo dokázáno, že asymptotická časová složitost žádného řadícího algoritmu založeného na porovnávání dvou prvků nemůže růst pomaleji než lineárně-logaritmicky v závislosti na počtu řazených prvků. Výpočet si totiž lze představit jako průchod binárním stromem, který má n! listů a každý z nich představuje jednu permutaci. Výška tohoto stromu je log(n!), což je asymptoticky n*log(n).
Formální definice
Nechť R1 až Rn jsou prvky určené k seřazení. Aby bylo množné prvky jednoznačně seřadit, musí existovat injektivní zobrazení f, které každému prvku přiřadí tzv. klíč. Množina všech klíčů generovaných tímto zobrazením musí být uspořádaná – každý klíč tedy musí být jednoznačně porovnatelný se všemi ostatními klíči. To znamená, že pro každou dvojici klíčů je možné jednoznačně určit, který z nich je větší, který menší, či zda se klíče rovnají. Klíč prvku Ri bude značen jako Ki. Seřadit prvky R1 až Rn znamená nalézt takovou jejich posloupnost, pro kterou platí:
Získávání klíče
Přirozená, celá a reálná čísla jsou triviálně uspořádaná a zároveň s nimi počítače umí dobře pracovat. Proto se v praxi často používají jako klíče. Řadí-li se například data, lze je převést na přirozená čísla tímto způsobem:
Znaky lze považovat za celá čísla, řetězce za posloupnosti čísel:
Protože prvky bývají mnohem objemnější než jejich klíče, řadící algoritmy pracují pouze s klíči. Jiné informace nejsou pro běh řadících algoritmů potřebné.
Vlastnosti řadících algoritmů
- časová složitost – přibližný řád růstu doby výpočtu v závislosti na počtu řazených prvků
- paměťová složitost -řád velikosti potřebné paměti v závislosti na počtu řazených prvků
- stabilita – stabilní řadící algoritmus zachovává relativní pořadí prvků se stejným klíčem
- přirozenost – rychlost přirozeného řadícího algoritmu roste s rostoucím podílem seřazených prvků na vstupu
Vícenásobné řazení
Řadící algoritmus se označuje jako stabilní pokud zachovává relativní pořadí prvků se stejným klíčem. Jsou-li například osoby seřazeny podle jména a řadí se podle příjmení, stabilní řadící algoritmus zachová abecední pořadí jmen, přestože o něm vůbec neví – již pouze nemění pořadí osob se stejným příjmením. Dalo by se o něm říci, že zbytečně nepřesouvá prvky, které nemusí.
Řadící algoritmy
Paralelní vnitřní řazení
| Algoritmus | Asymptotická časová složitost | Stabilní | Přirozený |
|---|---|---|---|
| Enumeration Sort | – | ano | ne |
| EOT Sort | – | – | – |
| Shear Sort | – | – | – |
Sekvenční vnitřní řazení
| Algoritmus | Asymptotická časová složitost | Stabilní | Přirozený |
|---|---|---|---|
| Selection Sort | až kvadratická | ne | ne |
| Insertion Sort | až kvadratická | ano | ano |
| Bubble Sort | až kvadratická | ano | ano |
| Quick Sort | lineárně-logaritmická až kvadratická | ano | ne |
| Merge Sort | lineárně-logaritmická | ano | ano |
| Heap Sort | lineárně-logaritmická | ne | ne |