Ďalším významným rozdielom medzi týmito dvomi je, že bublina je stabilný algoritmus, zatiaľ čo selekčný sortiment je nestabilný algoritmus. Algoritmus sa považuje za stabilný prvky s rovnakým kľúčom vyskytujúce sa v rovnakom poradí, ako sa vyskytovali pred triedením v zozname alebo poli. Všeobecne platí, že väčšina stabilných a rýchlych algoritmov používa dodatočnú pamäť.
Porovnávacia tabuľka
| Základ pre porovnanie | Triedenie bublín | Triedenie výberu |
|---|---|---|
| základné | Susediaci prvok je porovnávaný a vymenený | Najväčší prvok sa vyberie a vymení sa s posledným prvkom (v prípade vzostupného poradia). |
| Najlepšia časová náročnosť | O (n) | O (n2) |
| efektívnosť | neefektívne | Zlepšená účinnosť v porovnaní s triedením bublín |
| stabilný | Áno | žiadny |
| metóda | Zasielanie | výber |
| rýchlosť | pomaly | Rýchle v porovnaní s triedením bublín |
Definícia triedenia bublín
Triedenie bublín je najjednoduchší iteračný algoritmus, ktorý funguje porovnaním každej položky alebo prvku s položkou vedľa nej a v prípade potreby výmenou. Jednoducho povedané, porovná prvý a druhý prvok zoznamu a zmení ho, pokiaľ nie sú mimo špecifického poradia. Podobne sa druhý a tretí prvok porovnávajú a vymieňajú a toto porovnanie a výmena pokračujú na konci zoznamu. Počet porovnaní v prvej iterácii je n-1, kde n je počet prvkov v poli. Najväčší prvok by bol po novej pozícii po prvej iterácii. A po každej iterácii sa počet porovnaní znižuje a na poslednej iterácii sa uskutočňuje iba jedno porovnanie.
Tento algoritmus je najpomalší algoritmus triedenia. Najlepšia zložitosť prípadov (ak je zoznam v poriadku) typu Bubble je rádovo n ( O (n) ) a najhorší prípad je zložitosť O (n2) . V najlepšom prípade je to príkaz n, pretože to jednoducho porovnáva prvky a nevymieňa ich. Táto technika tiež vyžaduje dodatočný priestor na uloženie dočasnej premennej.
Definícia triedenia výberu
Triedenie výberu dosiahlo mierne lepší výkon a je efektívnejšie než algoritmus triedenia bublín. Predpokladajme, že chceme usporiadať pole vo vzostupnom poradí, potom funguje tým, že nájde najväčší prvok a vymení ho za posledný prvok a zopakuje nasledujúci proces na sub-arrays až do úplného zoradenia celého zoznamu.
Kľúčové rozdiely medzi triedením bublín a triedením výberu
- Pri triedení bublín sa každý prvok a jeho priľahlý prvok porovnávajú a v prípade potreby sa vymenia. Na druhej strane výber triedenia funguje výberom prvku a výmenou daného prvku za posledný prvok. Zvolený prvok by mohol byť najväčší alebo najmenší v závislosti od poradia, tj vzostupného alebo klesajúceho.
- Najhoršie zložitosť prípadov je rovnaká v obidvoch algoritmoch, tj O (n2), ale najlepšia zložitosť je odlišná. Triedenie bublín má poradie n čas, zatiaľ čo triedenie výberu spotrebuje poradie n2 času.
- Triedenie bublín je stabilný algoritmus, naopak selekčné triedenie je nestabilné.
- Algoritmus triedenia výberu je rýchly a účinný v porovnaní s triedením bublín, ktoré je veľmi pomalé a neefektívne.
záver
Algoritmus triedenia bublín sa považuje za najjednoduchší a neefektívny algoritmus, ale algoritmus triedenia výberu je efektívny v porovnaní s triedením bublín. Triedenie bublín tiež spotrebuje ďalší priestor na uloženie dočasnej premennej a potrebuje viac swapov.
