Rozdíl mezi tříděním bublin a tříděním vložení

Řazení bublin vs Vložení Ř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. Vkládací řazení je také třídicí algoritmus, který pracuje vložením prvku do seznamu vstupů na správnou pozici v seznamu, který je již tříděn. Tento proces se používá opakovaně, dokud není seznam setříděn.

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 vložení řazení?

Insertion sort je další třídicí algoritmus, který pracuje vložením prvku ve vstupním seznamu do správné pozice v seznamu (to je již tříděno). Tento proces se používá opakovaně, dokud není seznam setříděn. Při vkládání se třídění provádí na místě. Proto po iteraci algoritmu budou první položky i + 1 v seznamu seřazeny a zbytek seznamu bude netříděn. Při každé iteraci bude odebrán první prvek v netříděné části seznamu a vložen na správné místo v tříděné části seznamu. Vložení řazení má průměrnou časovou složitost O (n2). Z tohoto důvodu není řazení řazení vhodné ani pro třídění velkých seznamů.

Jaký je rozdíl mezi tříděním bublin a tříděním vložení?

Přestože oba algoritmy třídění bublin a vkládání mají průměrné složitosti času O (n2), je třídění bublin téměř vždy překonáno vložením. 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á. Také existuje varianta vloženého druhu nazvaná shell shell, která má časovou složitost O (n3 / 2), která by umožňovala jeho praktické použití. Kromě toho je řazení v porovnání s bublinovým tříděním velmi efektivní pro třídění „téměř tříděných“ seznamů.