Zoraďovanie podľa bubliny vs zoradenie podľa vloženia
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. Vloženie triedenia je tiež triediaci algoritmus, ktorý funguje tak, že prvok vo vstupnom zozname sa vloží na správnu pozíciu v zozname, ktorý je už zoradený. Tento proces sa opakuje, kým sa zoznam nezoradí.
Č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 vloženia?
Vloženie triedenia je ďalší triediaci algoritmus, ktorý funguje tak, že prvok vo vstupnom zozname sa vloží na správnu pozíciu v zozname (ktorý je už zoradený). Tento proces sa opakuje, kým sa zoznam nezoradí. Pri vkladaní sa triedenie vykonáva na mieste. Preto po i-tej iterácii algoritmu budú prvé položky i+1 v zozname zoradené a zvyšok zoznamu nebude zoradený. Pri každej iterácii sa vezme prvý prvok v nezoradenej časti zoznamu a vloží sa na správne miesto v triedenej časti zoznamu. Zoradenie vloženia má priemernú časovú zložitosť prípadu O(n2). Z tohto dôvodu nie je triedenie vkladania vhodné ani na triedenie veľkých zoznamov.
Aký je rozdiel medzi bublinkovým a vloženým triedením?
Aj keď algoritmy na triedenie podľa bublín aj na triedenie vkladania majú priemernú časovú zložitosť prípadu O(n2), triedenie podľa bublín takmer vždy prekonáva triedenie vkladania. 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á. Existuje aj variant inzertného triedenia nazývaný shell sort, ktorý má časovú zložitosť O(n3/2), čo by umožnilo jeho praktické využitie. Okrem toho je triedenie vložením v porovnaní s bublinovým triedením veľmi efektívne na triedenie „takmer zoradených“zoznamov.
