Sadržaj:
Definicija - Što znači Bubble Sort?
Bubble Sort je algoritam sortiranja koji djeluje tako što neprestano prolazi kroz popise koje je potrebno sortirati, uspoređujući svaki par susjednih stavki i zamjenjujući ih ako su pogrešnim redoslijedom. Ovaj postupak prolaska ponavlja se dok nisu potrebne zamjene, što ukazuje da je popis sortiran. Sorta mjehurića dobila je ime jer se manji elementi bubu prema vrhu popisa.
Sorta mjehurića se također naziva sorta tone ili usporedba.
Tehopedia objašnjava Bubble Sort
Sorta mjehurića ima najgori slučaj i prosječnu je složenost O (n2), gdje je n broj sortiranih predmeta. Za razliku od ostalih algoritama za razvrstavanje, vrsta mjehurića otkriva je li sortirani popis učinkovito ugrađen u algoritam. Učinkovitost razvrstavanja mjehurića na već razvrstanom popisu je O (n).
Položaj elemenata u vrsti mjehurića igra važnu ulogu u određivanju performansi. Veliki elementi na početku ne predstavljaju problem jer se lako mijenjaju. Mali elementi prema kraju polako se kreću prema početku. Kao takvi, ti se elementi nazivaju zečevima i kornjačama.
Algoritam sortiranja mjehurića može se optimizirati postavljanjem većih elemenata u krajnji položaj. Nakon svakog prolaza, svi elementi nakon posljednjeg swapa razvrstani su i nije ih potrebno ponovno provjeravati, čime se preskače praćenje zamijenjenih varijabli.
