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

Zoradenie bublín vs výber zoradenie

Bubble sort je algoritmus triedenia, ktorý funguje opakovaným prechádzaním zoznamom, ktorý sa má triediť, pri porovnaní párov susedných prvkov. Ak je pár prvkov v nesprávnom poradí, sú zamenené, aby sa umiestnili v správnom poradí. Tento prechod sa opakuje, až kým nie sú potrebné ďalšie výmeny. Výber zoradenia je tiež triediaci algoritmus, ktorý začína vyhľadaním minimálneho prvku v zozname a jeho výmenou za prvý prvok. Tento proces sa opakuje po zvyšok zoznamu umiestnením zamenených prvkov v poradí.

Čo je Bubble Sort?

Bubble sort je algoritmus triedenia, ktorý funguje opakovaným prechádzaním zoznamom, ktorý sa má triediť, pri porovnaní párov susedných prvkov. Ak je pár prvkov v nesprávnom poradí, sú zamenené, aby sa umiestnili v správnom poradí. Tento prechod sa opakuje, až kým nie sú potrebné ďalšie swapy (čo znamená, že zoznam je triedený). Pretože menšie prvky v zozname prichádzajú na povrch ako bublina na povrch, dostanú názov bubliny. Bublinové triedenie je veľmi jednoduchý algoritmus triedenia, ale pri triedení zoznamu s prvkami má priemernú časovú zložitosť prípadu O (n2). Z tohto dôvodu nie je triedenie bublín vhodné na triedenie zoznamov s veľkým počtom prvkov. Ale kvôli svojej jednoduchosti sa triedenie bubliniek vyučuje počas úvodov do algoritmov.

Čo je výberový výber?

Výber zoradenia je tiež ďalším triediacim algoritmom, ktorý začína vyhľadaním minimálneho prvku v zozname a jeho výmenou za prvý prvok. Potom sa minimálny prvok nájde od zvyšku zoznamu (od druhého prvku po posledný prvok v zozname) a zamení sa za druhý prvok. Tento proces sa opakuje po zvyšok zoznamu umiestnením zamenených prvkov v poradí. Pri výbere zoradenia je zoznam v ktoromkoľvek kroku algoritmu rozdelený na dve časti, kde jedna časť obsahuje zoradené prvky a druhá časť obsahuje netriedené prvky. Ako algoritmus pokračuje, triedený zoznam rastie zľava doprava. Triedenie výberu má tiež priemernú časovú zložitosť prípadu O (n2). Preto nie je vhodný ani na triedenie veľkých zoznamov.

Aký je rozdiel medzi triedením bublín a triedením výberu?

Aj keď algoritmy zoradenia bubliniek aj triedenia výberu majú priemernú zložitosť času prípadu O (n2), triedenie bubliniek je takmer vždy lepšie ako triedenie výberu. Je to kvôli počtu swapov, ktoré tieto dva algoritmy potrebujú (druh bubliny vyžaduje viac swapov). Ale kvôli jednoduchosti bublinového triedenia je jeho veľkosť kódu veľmi malá. Stabilita je ďalším rozdielom v týchto dvoch algoritmoch. Algoritmus stabilného triedenia je triediaci algoritmus, ktorý zachováva poradie záznamov, ak zoznam obsahuje prvky s rovnakou hodnotou. V tomto zmysle výberové usporiadanie nie je stabilný algoritmus, zatiaľ čo bublinové usporiadanie je stabilný algoritmus.