Rozdiel medzi radením bubliniek a vkladaním

Zoradenie bubliniek vs vkladanie

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. Vkladanie triedenia je tiež triediaci algoritmus, ktorý funguje vložením prvku do zoznamu vstupov na správne miesto v zozname, ktorý je už triedený. Tento proces sa používa opakovane, kým nie je zoznam zoradený.

Č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 triedenie inzercie?

Insertion sort je ďalší triediaci algoritmus, ktorý funguje vložením prvku do vstupného zoznamu na správne miesto v zozname (ktoré je už triedené). Tento proces sa používa opakovane, kým nie je zoznam zoradený. Pri vkladaní sa triedenie vykonáva na mieste. Preto po iterácii algoritmu budú prvé záznamy i + 1 v zozname zoradené a zvyšok zoznamu bude netriedený. Pri každej iterácii sa vyberie prvý prvok v netriedenej časti zoznamu a vloží sa na správne miesto v triedenej časti zoznamu. Typ vloženia má priemernú časovú zložitosť prípadu O (n2). Z tohto dôvodu nie je triedenie vkladaných položiek vhodné ani na triedenie veľkých zoznamov.

Aký je rozdiel medzi triedením bublín a triedením vloženia?

Aj keď algoritmy zoradenia bubliniek aj vloženia majú priemerné zložité časy O (n2), zoradenie bubliniek je takmer vždy prekonané vložením. 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á. Existuje aj variant vloženia, ktorý sa nazýva shell, ktorý má časovú zložitosť O (n3 / 2), čo by umožnilo jeho praktické využitie. Okrem toho je triedenie vkladania veľmi efektívne pri triedení „takmer triedených“ zoznamov v porovnaní s bublinovým triedením.