Odporúčaná, 2024

Redakcia Choice

Rozdiel medzi triedením bublín a triedením výberu

Triedenie je jednou z hlavných úloh v počítačových programoch, v ktorých sú prvky poľa usporiadané v určitom konkrétnom poradí. Triedenie umožňuje jednoduchšie vyhľadávanie. Zoradenie bublín a triedenie výberu sú triediace algoritmy, ktoré je možné diferencovať pomocou metód, ktoré používajú na triedenie. Triedenie bublín v podstate výmeny prvkov, zatiaľ čo triedenie výberu vykonáva triedenie výberom prvku.

Ď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 porovnanieTriedenie 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ívneZlepšená účinnosť v porovnaní s triedením bublín
stabilnýÁnožiadny
metódaZasielanievýber
rýchlosťpomalyRý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.

Pri selekčnom zoradení nie je triedené a nerozdelené pole nič iné a spotrebuje poradie n2 ( O (n2) ) v najhoršom i najhoršom prípade. Triedenie výberu je rýchlejšie ako triedenie bublín.

Kľúčové rozdiely medzi triedením bublín a triedením výberu

  1. 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.
  2. 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.
  3. Triedenie bublín je stabilný algoritmus, naopak selekčné triedenie je nestabilné.
  4. 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.

Top