Třídění podle bublin vs řazení vložení
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. Vložení řazení je také třídicí algoritmus, který funguje tak, že vloží prvek ve vstupním seznamu na správnou pozici v seznamu, který je již seřazen. Tento proces se opakuje, dokud není seznam seřazen.
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 bublina dostane na povrch, 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 řazení vložení?
Vložení třídění je další třídicí algoritmus, který funguje tak, že vloží prvek ve vstupním seznamu na správnou pozici v seznamu (který je již seřazen). Tento proces se opakuje, dokud není seznam seřazen. Při vkládání se třídění provádí na místě. Proto po i-té iteraci algoritmu budou první i+1 záznamy v seznamu seřazeny a zbytek seznamu bude neseřazen. Při každé iteraci se vezme první prvek v neseřazené části seznamu a vloží se na správné místo v seřazené části seznamu. Třídění vkládání má průměrnou časovou složitost případu O(n2). Z tohoto důvodu není řazení vložení vhodné ani pro řazení velkých seznamů.
Jaký je rozdíl mezi bublinovým řazením a řazením vložení?
Přestože jak algoritmy pro třídění podle bublin, tak algoritmy řazení vkládání mají průměrnou časovou složitost případu O(n2), řazení podle bublin téměř vždy překonává řazení vkládání. 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á. Existuje také varianta vkládání sort zvaná shell sort, která má časovou složitost O(n3/2), což by umožnilo její praktické použití. Kromě toho je řazení vložení velmi efektivní pro třídění „téměř seřazených“seznamů ve srovnání s bublinovým řazením.
