Deo zbornika Učimo algoritme

Ređanje mehurom (bubble sort)

Email Twitter LinkedIn Facebook Google

Ovo je jedna od najjednostavnijih metoda sortiranja koja je efikasna samo za relativno maleni broj elemenata. Za veći broj elemenata ova metoda je prespora. Stoga se vrlo retko upotrebljava osim za edukacijske svrhe.

Bubble sort algoritam u svakom prolazu kroz niz poredi uzastopne elemente, i razmenjuje im mesta ukoliko su u pogrešnom poretku. Prolasci kroz niz se ponavljaju sve dok se ne napravi prolaz u kome nije bilo razmena, što znači da je niz sortiran.

Primer

Prikažimo rad algoritma na primeru sortiranja niza (6 1 4 3 9):

Prvi prolaz:
(6 1 4 3 9) → (1 6 4 3 9), razmena jer je 6 > 1
(1 6 4 3 9) → (1 4 6 3 9), razmena jer je 6 > 4
(1 4 6 3 9) → (1 4 3 6 9), razmena jer je 6 > 3
(1 4 3 6 9) → (1 4 3 6 9)

Drugi prolaz:
(1 4 3 6 9) → (1 4 3 6 9)
(1 4 3 6 9) → (1 3 4 6 9), razmena jer 4 > 3
(1 3 4 6 9) → (1 3 4 6 9)
(1 3 4 6 9) → (1 3 4 6 9)

Treći prolaz:
(1 3 4 6 9) → (1 3 4 6 9)
(1 3 4 6 9) → (1 3 4 6 9)
(1 3 4 6 9) → (1 3 4 6 9)
(1 3 4 6 9) → (1 3 4 6 9)

Primetimo da je niz bio sortiran već nakon drugog prolaza, međutim, da bi se to utvrdilo, potrebno je bilo napraviti još jedan prolaz.

Naredna funkcija bubble sort algoritmom sortira niz a, dužine n.

void bubblesort(int a[], int n) {
  int bilo_razmena, i;
  do {
    bilo_razmena = 0;
    for (i = 0; i < n - 1; i++)
      if (a[i] > a[i + 1]) {
        razmeni(a, i, i+1);
        bilo_razmena = 1;
      }
  } while (bilo_razmena);
}

Uslov koji obezbeđuje parcijalnu korektnost je da ako bilo_razmena ima vrednost 0 pre provere uslova izlaska iz spoljašnje petlje, onda je niz a sortiran (tj. njegov početni deo dužine n). Zaista, kada se spoljašnja petlja završi, vrednost promenljive bilo_razmena je 0, te prethodna implikacija obezbeđuje korektnost. Invarijanta unutrašnje petlje koja obezbeđuje pomenuti uslov je da ako promenljiva bilo_razmena ima vrednost 0, onda je deo niza a[0, i] sortiran. Zaista, po završetku unutrašnje petlje i ima vrednost n-1, te je pomenuti uslov obezbeđen. Pošto je algoritam zasnovan na razmenama, invarijanta algoritma je i da se (multi)skup elemenata niza ne menja tokom njegovog izvršavanja.

Svojstvo algoritma koje obezbeđuje zaustavljanje je da nakon svake iteracije spoljašnje petlje sledeći najveći elemenat koji nije već bio na svojoj poziciji dolazi na nju. Bubble sort je na osnovu ovog svojstva i dobio ime (jer veliki elementi kao mehurići „isplivavaju“ ka kraju niza). Ovo sa jedne strane obezbeđuje zaustavljanje algoritma, dok se sa druge strane može iskoristiti za optimizaciju. Ovom optimizacijom se može smanjiti broj poređenja, ali ne i broj razmena.

void bubblesort(int a[], int n) {
  do {
    int i;
    for (i = 0; i < n - 1; i++)
      if (a[i] > a[i + 1])
        razmeni(a, i, i+1);
    n--;
  } while (n > 1);
}

Isti algoritam, može biti implementiran i na stilski malo drugačiji način (koji se može ponekad sresti u literaturi).

void bubblesort(int a[], int n) {
  int i, j;
  for (i = n - 1; i > 0; i--)
    for (j = 0; j < i; j++)
      if (a[j] > a[j + 1])
        razmeni(a, j, j+1);
}

Optimizacija može otići i korak dalje, ukoliko se dužina ne smanjuje samo za 1, već ukoliko se posmatra koliko je zaista elemenata na kraju niza već postavljeno na svoje mesto (ovo se može odrediti na osnovu mesta gde se dogodila poslednja zamena).

void bubblesort(int a[], int n) {
  do {
    int nn = 1, i;
    for (i = 0; i < n - 1; i++)
      if (a[i] > a[i + 1]) {
        razmeni(a, i, i+1);
        nn = i + 1;
      }
    n = nn;
  } while (n > 1);
}

U ovom slučaju, uslov koji važi pre provere uslova spoljašnje petlje je da su elementi od pozicije n-1 do kraja niza sortirani. Ovo obezbeđuje invarijanta unutrašnje petlje koja obezbeđuje da su svi elementi a[nn-1, i] sortirani.

Što se efikasnosti tiče, najgori slučaj nastupa kada su elementi početnog niza sortirani u opadajućem poretku. U tom slučaju vrši se n prolaska kroz niz, a u svakom prolasku se pravi n poređenja i n razmena, što ukupno daje O(n^2) poređenja i O(n^2) razmena. Primetimo da se optimizacijom broj poređenja smanjuje oko dva puta.

Bubble sort algoritam se smatra veoma lošim algoritmom. Neki autori čak zagovaraju tezu da bi ga trebalo potpuno izbaciti iz nastave računarstva. U šali se čak navodi kako bi jedini algoritam gori od njega bio algoritam koji permutuje niz na slučajan način sve dok slučajno ne postane sortiran.

Izvor: Predrag Janičić i Filip Marić, PROGRAMIRANJE 2, Osnove programiranja kroz programski jezik C, Matematički fakultet, Beograd, 2017.