Tři kvadratická třídění a čím se doopravdy liší
Všechna tři jsou O(n²) a přesto se chovají různě. Rozdíl je vidět nejlíp na tom, která část pole je už hotová.
| bublinkové | vkládáním | výběrem | |
|---|---|---|---|
| hotové roste | zprava | — | zleva |
| porovnání (nejhůř) | n(n−1)/2 | n(n−1)/2 | n(n−1)/2 |
| porovnání (setříděné) | n−1 | n−1 | n(n−1)/2 |
| přesunů (nejhůř) | n² | n² | n−1 |
| stabilní | ano | ano | ne |
Tři věci z té tabulky, které stojí za zapamatování
1. Třídění výběrem nemá nejlepší případ. Vždycky prochází celý zbytek, takže setříděné pole ho stojí přesně tolik co obrácené. Je to jediný z těch tří, u kterého se dá dopředu říct přesný počet porovnání, aniž by se člověk podíval na data.
2. Zato dělá nejmíň přesunů ze všech. Nejvýš n−1 výměn, protože každý prvek položí na místo jednou a hotovo. Když je zápis drahý — paměť flash s omezeným počtem cyklů, položka přes síť — je to najednou ten nejrozumnější kvadratický algoritmus, ačkoli porovnání dělá stejně jako ostatní.
3. Třídění vkládáním je na skoro setříděných datech výborné. Když je každý prvek nejvýš k pozic od svého místa, stojí to O(n·k). Proto se nevyhodilo: je vestavěné uvnitř rychlých knihovních sortů jako jejich koncový případ. Kapitola 6 ukáže, od jaké velikosti.
Stabilita je vlastnost, na kterou se zapomíná, dokud nechybí. Stabilní třídění zachová vzájemné pořadí prvků, které jsou si rovné. Když se tabulka setřídí nejdřív podle jména a pak stabilně podle oddělení, vyjde seřazená podle oddělení a uvnitř podle jména — zadarmo. S nestabilním tříděním to první seřazení zmizí.
Bublinkové třídění: proč se pořád učí a proč se nepoužívá
Nemá žádnou výhodu proti třídění vkládáním — dělá tolik porovnání a víc přesunů. Učí se, protože je nejjednodušší na vysvětlení, a to je jeho jediná role. V produkčním kódu není důvod ho napsat.