Dalším významným rozdílem mezi těmito dvěma je, že třídění bublin je stabilní algoritmus, zatímco výběrový druh je nestabilní algoritmus. Algoritmus je považován za stabilní elementy se stejným klíčem vyskytujícím se ve stejném pořadí, v jakém se vyskytovaly před zařazením do seznamu nebo pole. Obecně platí, že většina stabilních a rychlých algoritmů využívá přídavnou paměť.
Srovnávací graf
| Základ pro srovnání | Bubble sort | Výběr druhu |
|---|---|---|
| Základní | Sousední prvek je porovnán a vyměněn | Největší prvek je vybrán a vyměněn s posledním prvkem (v případě vzestupného pořadí). |
| Nejlepší případ složitost | Na) | O (n 2 ) |
| Účinnost | Neefektivní | Vyšší účinnost ve srovnání s tříděním bublin |
| Stabilní | Ano | Ne |
| Metoda | Výměna | Výběr |
| Rychlost | Zpomalit | Rychlý ve srovnání s druhem bublin |
Definice třídění bublin
Třídění bublin je nejjednodušší iterační algoritmus, který funguje porovnáním každé položky nebo prvku s položkou vedle ní a jejich případným přepínáním. V jednoduchých slovech porovnává první a druhý prvek seznamu a vyměňuje je, pokud nejsou mimo konkrétní pořadí. Podobně, druhý a třetí prvek jsou porovnány a zaměněny a toto porovnání a výměna přechází na konec seznamu. Počet porovnávání v první iteraci je n-1, kde n je počet prvků v poli. Největší prvek by byl na n-té pozici po první iteraci. Po každé iteraci se počet srovnávání snižuje a na poslední iteraci probíhá pouze jedno srovnání.
Tento algoritmus je nejpomalejším třídícím algoritmem. Nejlepší případová složitost (Když je seznam v pořádku) tříd Bubble je řádu n ( O (n) ) a nejhorší případová složitost je O (n2) . V nejlepším případě se jedná o řád n, protože prvky porovnává a nevyměňuje. Tato technika také vyžaduje další prostor pro uložení dočasné proměnné.
Definice třídění výběru
Výběrový druh dosáhl o něco lepšího výkonu a je efektivní než algoritmus třídění bublin. Předpokládejme, že chceme uspořádat pole ve vzestupném pořadí, pak to funguje tak, že najdeme největší prvek a vymění ho s posledním prvkem, a opakujeme následující postup na dílčích polích, dokud není celý seznam tříděn.
Rozdíly klíčů mezi tříděním bublin a výběrem řazení
- Při třídění bublin se každý prvek a jeho přilehlý prvek porovnávají a v případě potřeby vyměňují. Na druhou stranu výběrový výběr funguje tak, že vybere prvek a přepne daný prvek s posledním prvkem. Vybraný prvek může být největší nebo nejmenší v závislosti na pořadí, tj. Vzestupně nebo sestupně.
- Nejhorší případová složitost je stejná v obou algoritmech, tj. O (n2), ale nejlepší složitost je odlišná. Třídění bublin má pořadí n času, zatímco výběrový druh spotřebuje řád n2 času.
- Třídění bublin je stabilní algoritmus, naopak výběr je nestabilní.
- Výběrový algoritmus výběru je rychlý a efektivní ve srovnání s tříděním bublin, které je velmi pomalé a neefektivní.
Závěr
Algoritmus třídění bublin je považován za nejjednodušší a neefektivní algoritmus, ale algoritmus třídění výběru je účinný ve srovnání s tříděním bublin. Bubble sort také spotřebovává další prostor pro ukládání dočasné proměnné a potřebuje více swapů.
