Rozdíl mezi tříděním bublin a tříděním výběru

Řazení bublin vs Výběr Řadit

Bubble sort je algoritmus třídění, který funguje opakovaným procházením seznamem, který se má třídit, při porovnávání dvojic sousedících prvků. Pokud je pár prvků v nesprávném pořadí, jsou zaměněny za správné umístění. Tento průchod se opakuje, dokud nejsou zapotřebí žádné další swapy. Výběr řazení je také třídicí algoritmus, který začíná vyhledáním minimálního prvku v seznamu a jeho výměnou s prvním prvkem. Tento proces se opakuje po zbytek seznamu umístěním zaměněných prvků v pořadí.

Co je Bubble Sort?

Bubble sort je algoritmus třídění, který funguje opakovaným procházením seznamem, který se má třídit, při porovnávání dvojic sousedících prvků. Pokud je pár prvků v nesprávném pořadí, jsou zaměněny za správné umístění. Tento průchod se opakuje, dokud nejsou potřeba žádné další swapy (což znamená, že je seznam seřazen). Vzhledem k tomu, že menší prvky v seznamu přicházejí na vrchol, když se bublina dostane na povrch, dostane se název bubliny. Bubble sort je velmi jednoduchý algoritmus třídění, ale při třídění seznamu podle n prvků má průměrnou složitost času O (n2). Z tohoto důvodu není řazení bublin vhodné pro třídění seznamů s velkým počtem prvků. Ale kvůli své jednoduchosti je třídění bublin učeno během úvodů do algoritmů.

Co je výběr řazení?

Třídění výběru je také další algoritmus třídění, který začíná vyhledáním minimálního prvku v seznamu a jeho zaměněním s prvním prvkem. Pak je minimální prvek nalezen od zbytku seznamu (od druhého prvku po poslední prvek v seznamu) a zaměněn za druhý prvek. Tento proces se opakuje po zbytek seznamu umístěním zaměněných prvků v pořadí. Takže při výběru řazení je v kterémkoli kroku algoritmu seznam rozdělen do dvou částí, kde jedna část obsahuje tříděné prvky a druhá část obsahuje netříděné prvky. Jak algoritmus pokračuje, setříděný seznam roste zleva doprava. Výběrové řazení má také průměrnou časovou složitost O (n2). Proto také není vhodný pro třídění velkých seznamů.

Jaký je rozdíl mezi tříděním bublin a tříděním výběru?

Přestože jak algoritmy třídění bublin, tak třídění výběru mají průměrné složitosti času O (n2), je třídění bublin téměř vždy lepší než třídění výběru. Je to kvůli počtu swapů, které tyto dva algoritmy potřebují (druhy bublin vyžadují více swapů). Ale kvůli jednoduchosti třídění bublin je jeho velikost kódu velmi malá. Stabilita je dalším rozdílem v těchto dvou algoritmech. Algoritmus stabilního třídění je třídicí algoritmus, který zachovává pořadí záznamů, pokud seznam obsahuje prvky se stejnou hodnotou. V tomto smyslu není výběrové řazení stabilní algoritmus, zatímco bublinové řazení je stabilní algoritmus.