Razvrščanje oblačkov v primerjavi z razvrščanjem izbire
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. Izbirno razvrščanje je tudi algoritem za razvrščanje, ki se začne z iskanjem minimalnega elementa na seznamu in zamenjavo s prvim elementom. Ta postopek se ponovi za preostanek seznama tako, da se zamenjani elementi postavijo po vrstnem redu.
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 izbire?
Razvrščanje izbire je tudi drug algoritem za razvrščanje, ki se začne z iskanjem minimalnega elementa na seznamu in zamenjavo s prvim elementom. Nato najdemo minimalni element iz preostalega dela seznama (od drugega elementa do zadnjega elementa na seznamu) in ga zamenjamo z drugim elementom. Ta postopek se ponovi za preostanek seznama tako, da se zamenjani elementi postavijo po vrstnem redu. Torej je pri izbirnem razvrščanju na katerem koli koraku algoritma seznam razdeljen na dva dela, kjer en del vsebuje razvrščene elemente, drugi del pa nesortirane elemente. Ko algoritem napreduje, razvrščeni seznam raste od leve proti desni. Izbirno razvrščanje ima tudi povprečno časovno kompleksnost primera O(n2). Zato tudi ni primeren za razvrščanje velikih seznamov.
Kakšna je razlika med Bubble Sort in Selection Sort?
Čeprav imata tako algoritma mehurčkastega razvrščanja kot izbirnega razvrščanja povprečno zahtevnost primera O(n2), je mehurčkasto razvrščanje skoraj vedno boljše od izbirnega razvrščanja. 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. Stabilnost je še ena razlika v teh dveh algoritmih. Stabilen algoritem za razvrščanje je algoritem za razvrščanje, ki ohrani vrstni red zapisov, če seznam vsebuje elemente z enako vrednostjo. V tem smislu izbirno razvrščanje ni stabilen algoritem, medtem ko je razvrščanje z mehurčki stabilen algoritem.
