Mehurčno urejanje
Mehurčno urejanje | |
---|---|
![]() Grafični prikaz mehurčnega urejanja | |
Osnovni podatki | |
Vrsta: | algoritem za urejanje podatkov |
Podatkovna struktura: | tabela |
Časovna zahtevnost | |
Zgornja meja zahtevnosti: | O(n2) |
Spodnja meja zahtevnosti: | O(n) |
Pričakovana zahtevnost: | O(n2) |
Prostorska zahtevnost | |
Prostorska zahtevnost: | O(1) |
Mehurčno urejanje ali navadne zamenjave (angleško BubbleSort) je algoritem za urejanje podatkov, s katerim uredimo vrstni red elementov v tabeli po velikosti. Deluje tako, da manjši oz. večji elementi potujejo po tabeli navzgor oz. navzdol. Algoritem je dobil tako ime, ker elementi navidez potujejo kot mehurčki proti površini.
Delovanje
[uredi | uredi kodo]Algoritem začne iteracijo na začetku tabele. Najprej primerja prva dva elementa in če je prvi element večji od drugega, ju zamenja. Nato primerja drugi in tretji element in ju, če je potrebno, zamenja in tako naprej do konca tabele. Na koncu te iteracije smo dokončno uredili vsaj en element (zadnji), zato se lahko naslednja iteracija ustavi en element prej in vsaka naslednja iteracija še en element prej. Ko se izteče ena iteracija v kateri ne naredimo nobene zamenjave, je tabela urejena, zato algoritem končamo.
![](http://upload.wikimedia.org/wikipedia/sl/thumb/5/55/Bubble_sort.png/200px-Bubble_sort.png)
Zahtevnost
[uredi | uredi kodo]Časovna zahtevnost mehurčnega urejanja je v najslabšem in povprečnem primeru , v najboljšem (če je tabela že urejena) pa . Prostorska zahtevnost pa je , saj urejamo na mestu.
Psevdokoda
[uredi | uredi kodo] zamenjano = true;
neurejenih = length(tabela);
while (zamenjano == true) {
zamenjano = false;
neurejenih--;
for (i = 0; i < neurejenih; i++) {
if (tabela[i] > tabela[i+1]) {
zamenjaj(i, i+1);
zamenjano = true;
}
}
}