Stabilní řazení

Řadicí algoritmus je stabilní tehdy, jestliže po seřazení zachovává vzájemné pořadí prvků se stejným klíčem.

Jinými slovy: Mějme množinu prvků M. Pro každé dva prvky R a S o stejném klíči z této množiny platí, že pokud byl prvek R v neseřazené množině před prvkem S, pak je i v seřazené posloupnosti prvek R před prvkem S. Pokud tato vlastnost platí pro všechny možné množiny M, pak je algoritmus stabilní.

Příklady

Řazení jmen a příjmení

Mějme seznam jmen a příjmení reprezentovaný uspořádanou dvojicí ${\displaystyle (A,B)}$, kde ${\displaystyle A}$ je jméno a ${\displaystyle B}$ je příjmení. Seznam vypadá takto: ${\displaystyle (a,z),(b,x),(b,y)}$.

Po seřazení stabilním algoritmem bude výsledek vždy vypadat takto: ${\displaystyle (a,z),(b,x),(b,y)}$.

Pokud by byl použit nestabilní řadící algoritmus, výsledek by mohl vypadat takto: ${\displaystyle (a,z),(b,y),(b,x)}$.

Města a okresy

Máme-li seznam českých měst seřazený abecedně dle názvu a necháme-li ho seřadit stabilním řadicím algoritmem dle okresů, budou v seznamu města seřazena dle okresů, ale v rámci každého okresu zůstane zachováno abecední řazení dle názvu. Pokud bychom použili algoritmus, který není stabilní, tak toto zaručeno nemáme.

Příklady stabilních algoritmů

• bublinkové řazení
• řazení vkládáním
• řazení slučováním
• přihrádkové řazení
• číslicové řazení
• Counting sort (řazení počítáním četností)