Razvrščanje z oblački proti razvrščanju z vstavljanjem
Bubble sort je algoritem za razvrščanje, ki deluje tako, da gre skozi seznam, ki ga je treba razvrstiti večkrat, medtem ko primerja pare elementov, ki so sosednji. Če je par elementov v napačnem vrstnem redu, se zamenjajo, da se postavijo v pravilnem vrstnem redu. To prečkanje se ponavlja, dokler niso potrebne nadaljnje zamenjave. Razvrščanje z vstavljanjem je tudi algoritem za razvrščanje, ki deluje tako, da element v vhodnem seznamu vstavi na pravilno mesto v seznamu, ki je že razvrščen. Ta postopek se ponavlja, dokler seznam ni razvrščen.
Kaj je Bubble Sort?
Bubble sort je algoritem za razvrščanje, ki deluje tako, da gre skozi seznam, ki ga je treba razvrstiti večkrat, medtem ko primerja pare elementov, ki so sosednji. Če je par elementov v napačnem vrstnem redu, se zamenjajo, da se postavijo v pravilnem vrstnem redu. To prečkanje se ponavlja, dokler niso potrebne nadaljnje zamenjave (kar pomeni, da je seznam razvrščen). Ker pridejo manjši elementi na seznamu na vrh, ko mehurček pride na površje, se imenuje razvrščanje mehurčkov. Razvrščanje z mehurčki je zelo preprost algoritem za razvrščanje, vendar ima povprečno zahtevnost primera O(n2) pri razvrščanju seznama z n elementi. Zaradi tega mehurčkasto razvrščanje ni primerno za razvrščanje seznamov z velikim številom elementov. Toda zaradi svoje preprostosti se mehurčkasto razvrščanje učijo med uvodom v algoritme.
Kaj je razvrščanje z vstavljanjem?
Razvrščanje z vstavljanjem je še en algoritem za razvrščanje, ki deluje tako, da element v vhodnem seznamu vstavi na pravilno mesto na seznamu (ki je že razvrščen). Ta postopek se ponavlja, dokler ni seznam razvrščen. Pri razvrščanju z vstavljanjem se razvrščanje izvede na mestu. Zato bo po i-ti ponovitvi algoritma prvih i+1 vnosov na seznamu razvrščenih, preostali del seznama pa nerazvrščenih. Pri vsaki ponovitvi bo prvi element v nerazvrščenem delu seznama vzet in vstavljen na pravilno mesto v razvrščenem delu seznama. Razvrščanje pri vstavljanju ima povprečno časovno zapletenost primera O(n2). Zaradi tega tudi razvrščanje z vstavljanjem ni primerno za razvrščanje velikih seznamov.
Kakšna je razlika med Bubble Sort in Insertion Sort?
Čeprav imata algoritma mehurčkastega razvrščanja in razvrščanja z vstavljanjem povprečno zapletenost primera O(n2), je razvrščanje z mehurčki skoraj ves čas boljše od razvrščanja z vstavljanjem. To je posledica števila zamenjav, ki jih potrebujeta oba algoritma (razvrščanje z mehurčki potrebuje več zamenjav). Toda zaradi preprostosti mehurčkovega razvrščanja je njegova velikost kode zelo majhna. Obstaja tudi različica razvrščanja z vstavljanjem, imenovana lupinsko razvrščanje, ki ima časovno kompleksnost O(n3/2), kar bi omogočilo njegovo praktično uporabo. Poleg tega je razvrščanje z vstavljanjem zelo učinkovito za razvrščanje "skoraj razvrščenih" seznamov v primerjavi z razvrščanjem z mehurčki.
