Třídění podle bublin vs. řazení podle výběru
Bubble sort je třídicí algoritmus, který funguje tak, že prochází seznam, který má být seřazen, opakovaně a přitom porovnává dvojice prvků, které spolu sousedí. Pokud je pár prvků ve špatném pořadí, jsou zaměněny, aby byly umístěny ve správném pořadí. Toto procházení se opakuje, dokud nejsou vyžadovány žádné další swapy. Třídění výběru je také třídicí algoritmus, který začíná nalezením minimálního prvku v seznamu a jeho záměnou za první prvek. Tento proces se opakuje pro zbytek seznamu umístěním vyměněných prvků v pořadí.
Co je bublinové třídění?
Bubble sort je třídicí algoritmus, který funguje tak, že prochází seznam, který má být seřazen, opakovaně a přitom porovnává dvojice prvků, které spolu sousedí. Pokud je pár prvků ve špatném pořadí, jsou zaměněny, aby byly umístěny ve správném pořadí. Toto procházení se opakuje, dokud nejsou vyžadovány žádné další swapy (což znamená, že seznam je setříděn). Vzhledem k tomu, že se menší prvky v seznamu dostanou na začátek, když se na povrch dostane bublina, dostane název bublinové řazení. Bublinové třídění je velmi jednoduchý třídicí algoritmus, ale má průměrnou časovou složitost případu O(n2) při třídění seznamu s n prvky. Bublinové řazení se kvůli tomu nehodí pro řazení seznamů s velkým počtem prvků. Ale díky své jednoduchosti se bublinové třídění učí během úvodu do algoritmů.
Co je třídění výběru?
Selekce řazení je také další třídicí algoritmus, který začíná nalezením minimálního prvku v seznamu a jeho záměnou za první prvek. Poté je nalezen minimální prvek ze zbytku seznamu (od druhého prvku po poslední prvek v seznamu) a zaměněn za druhý prvek. Tento proces se opakuje pro zbytek seznamu umístěním prohozených prvků do pořadí. Takže při třídění výběru se v kterémkoli kroku algoritmu seznam rozdělí na dvě části, kde jedna část obsahuje seřazené prvky a druhá část obsahuje neseřazené prvky. Jak algoritmus pokračuje, seřazený seznam roste zleva doprava. Výběrové řazení má také průměrnou časovou složitost případu O(n2). Proto také není vhodný pro třídění velkých seznamů.
Jaký je rozdíl mezi bublinovým řazením a tříděním výběru?
Přestože jak algoritmy pro třídění podle bublin, tak algoritmy třídění podle výběru mají průměrnou časovou složitost případu O(n2), třídění podle bublin téměř vždy překonává třídění podle výběru. To je způsobeno počtem swapů, které tyto dva algoritmy potřebují (bublinové řazení vyžaduje více swapů). Ale kvůli jednoduchosti bublinového třídění je velikost jeho kódu velmi malá. Stabilita je dalším rozdílem v těchto dvou algoritmech. Stabilní třídicí algoritmus je třídicí algoritmus, který zachovává pořadí záznamů, pokud seznam obsahuje prvky se stejnou hodnotou. V tomto smyslu není třídění výběru stabilním algoritmem, zatímco řazení podle bublin je stabilní algoritmus.
