Triedenie podľa bubliny verzus triedenie výberu
Bubble sort je triediaci algoritmus, ktorý funguje tak, že opakovane prechádza zoznam, ktorý sa má triediť, pričom porovnáva páry prvkov, ktoré susedia. Ak je pár prvkov v nesprávnom poradí, vymenia sa, aby sa umiestnili v správnom poradí. Toto prechádzanie sa opakuje, kým nie sú potrebné žiadne ďalšie výmeny. Triedenie výberu je tiež triediaci algoritmus, ktorý začína nájdením minimálneho prvku v zozname a jeho zámenou za prvý prvok. Tento proces sa opakuje pre zvyšok zoznamu umiestnením vymenených prvkov v poradí.
Čo je bublinové triedenie?
Bubble sort je triediaci algoritmus, ktorý funguje tak, že opakovane prechádza zoznam, ktorý sa má triediť, pričom porovnáva páry prvkov, ktoré susedia. Ak je pár prvkov v nesprávnom poradí, vymenia sa, aby sa umiestnili v správnom poradí. Toto prechádzanie sa opakuje, kým nie sú potrebné žiadne ďalšie výmeny (čo znamená, že zoznam je zoradený). Keďže menšie prvky v zozname sa dostanú na začiatok, keď sa bublina dostane na povrch, dostane názov bublinové triedenie. Bublinové triedenie je veľmi jednoduchý triediaci algoritmus, ale pri triedení zoznamu s n prvkami má priemernú časovú zložitosť prípadu O(n2). Bublinové triedenie z tohto dôvodu nie je vhodné na triedenie zoznamov s veľkým počtom prvkov. Ale kvôli svojej jednoduchosti sa bublinové triedenie učí počas úvodu do algoritmov.
Čo je triedenie výberu?
Triedenie výberu je tiež ďalší triediaci algoritmus, ktorý začína nájdením minimálneho prvku v zozname a jeho zámenou za prvý prvok. Potom sa nájde minimálny prvok zo zvyšku zoznamu (od druhého prvku po posledný prvok v zozname) a vymení sa za druhý prvok. Tento proces sa opakuje pre zvyšok zoznamu umiestnením vymenených prvkov do poradia. Takže pri triedení výberu sa v ktoromkoľvek kroku algoritmu zoznam rozdelí na dve časti, pričom jedna časť obsahuje zoradené prvky a druhá časť obsahuje nezoradené prvky. Ako algoritmus pokračuje, zoradený zoznam rastie zľava doprava. Výberové triedenie 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 bublinkovým a výberovým triedením?
Aj keď algoritmy na triedenie podľa bublín, aj na triedenie podľa výberu majú priemernú časovú zložitosť prípadu O(n2), triedenie podľa bublín takmer vždy prekonáva triedenie podľa výberu. Je to kvôli počtu swapov, ktoré tieto dva algoritmy potrebujú (bublinkové triedenie potrebuje viac swapov). Ale kvôli jednoduchosti bublinového triedenia je veľkosť jeho kódu veľmi malá. Stabilita je ďalším rozdielom v týchto dvoch algoritmoch. Stabilný triediaci algoritmus je triediaci algoritmus, ktorý zachováva poradie záznamov, ak zoznam obsahuje prvky s rovnakou hodnotou. V tomto zmysle triedenie výberu nie je stabilný algoritmus, zatiaľ čo triedenie podľa bublín je stabilný algoritmus.
