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.

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)

Delovanje uredi

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.

 
Sortiranje polja od najmanjšega do največjega

Zahtevnost uredi

Č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

  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;
          }
      }      
  }