Sortiranje mehurom

Sortiranje mehurom

Vizuelna predstava bablsort algoritma
Klasa	Algoritam sortiranja
Struktura podataka	Niz
Najgora performanca	$O(n^{2})$
Najbolja performanca	$O(n)$
Prosečna performanca	$O(n^{2})$
Najgora prostorna kompleksnost	$O(1)$

Sortiranje mehurom ili Bablsort (engl. Bubble sort), ponekad pogrešno nazvano potapajuće sortiranje, algoritam je koji se koristi za sortiranje nizova. Algoritam radi tako što upoređuje svaka dva susedna člana niza i zamenjuje im mesta, ako su članovi niza u pogrešnom redosledu. Prolazi se kroz niz elemenata sve dok se ne izvrši nijedna zamena tj. elementi su sortirani u odgovarajućem poretku (rastućem ili opadajućem). Naziv vodi poreklo od činjenice da se posle prve iteracije kroz niz najveći element nalazi na najvećoj poziciji u nizu, tj. na desnoj strani niza. Algoritam je veoma lak za implementaciju u svim programskim jezicima, ali je veoma nepraktičan i spor čak i kada se uporedi sa algoritmom kao što je sortiranje umetanjem. Algoritam radi dobro na nizovima koji ima mali broj elemenata, ili koji su polusortirani, tj. samo određeni broj elemenata je na nepravilnim pozicijama.

Analiza

Primer bubble sorta. Polazi se od početka niza, uproredjuje svaki susedni par i menja njihov položaj, ako nisu u pravom redosledu (sledeći je manji od prethodnog). Posle svake iteracije, upoređuje se jedan element manje, sve dok više ne postoje elementi koje treba upoređivati.

Performanse

Bablsort ima najgoru složenost О(n²), gde je n broj elemenata koji se sortiraju. Postoji mnogo algoritama za sortiranje koji imaju znatno bolju složenost O(n log n). Čak i drugi algoritimi složenosti О(n²), kao što je sortiranje umetanjem, imaju tendenciju da imaju bolje performanse od bablsorta. Dakle, sortiranje mehurom nije praktičan algoritam za sortiranje kada je n veliko.

Jedina značajna prednost bablsorta za razliku od drugih implementacija, čak i kviksorta, ali ne sortiranja umetanjem, je sposobnost da otkrije da je sortiran niz efikasno ugrađen u algoritam. Složenost bablsorta nad već sortiranim nizovima (u najboljem slučaju) je O(n). Nasuprot tome, većina drugih algoritama, čak i oni sa boljom prosečnom složenošću, obavljaju ceo proces sortiranja na setu i na taj način su složeniji. Međutim, ne samo da insertion sort ima ovaj mehanizam, već i bolje radi na nizu koji je znatno sortiran (mali broj inverzija)

Zečevi i kornjače

Pozicije elemenata u bablsortu igraju veliku ulogu u određivanju složenosti. Veliki elementi na početku niza ne predstavljaju problem jer se brzo zamene. Mali elementi pri kraju niza se kreću na početak veoma sporo. Zbog toga se ove vrste elemenata respektivno nazivaju zečevi i kornjače.

Učinjeni su razni napori da se eliminišu kornjače kako bi se poboljšala brzina bablsorta. Koktelsort je dvosmerni bablsort koji ide od početka do kraja, a onda se poništava i ide od kraja do početka. On može da se pomera kornjače prilično dobro, ali zadržava složenost O(n²). Kombsort poredi elemente razdvojene velikim prazninama, a može da pomera kornjače izuzetno brzo pre nego što pređe na manje praznine. Njegova prosečna brzina se može uporediti sa brzim algoritmima kao što je kviksort.

Korak po korak primer

Niz brojeva "5 1 4 2 8" potrebno je sortirati od najmanjeg do najvećeg broja (u rastućem poretku) pomoću bablsorta. U svakom koraku boldirani elementi se upoređuju. Biće potrebna tri prolaska kroz niz:

Prvi prolazak:

(5 1 4 2 8 ) $\to$ (1 5 4 2 8 ), Algoritam upoređuje prva dva elementa i zamenjuje 1 i 5 , 5 > 1.

(1 5 4 2 8 ) $\to$ (1 4 5 2 8 ), zamena pošto je 5 > 4

(1 4 5 2 8 ) $\to$ (1 4 2 5 8 ), zamena pošto je 5 > 2

(1 4 2 5 8 ) $\to$ (1 4 2 5 8 ), Sada, pošto su ovi elementi već sortirani (8 > 5), algoritam ih neće zameniti.

Drugi prolazak:

(1 4 2 5 8 ) $\to$ (1 4 2 5 8 )

(1 4 2 5 8 ) $\to$ (1 2 4 5 8 ), zamena pošto je 4 > 2

(1 2 4 5 8 ) $\to$ (1 2 4 5 8 )

(1 2 4 5 8 ) $\to$ (1 2 4 5 8 )

Sada, niz je već sortiran, ali naš algoritam još uvek ne zna da je sortiranje završeno. Algoritam je završen tek kada prodje kroz ceo niz bez i jedne zamene.

Treći prolazak:

(1 2 4 5 8 ) $\to$ (1 2 4 5 8 )

(1 2 4 5 8 ) $\to$ (1 2 4 5 8 )

(1 2 4 5 8 ) $\to$ (1 2 4 5 8 )

(1 2 4 5 8 ) $\to$ (1 2 4 5 8 )

Implementacija

Pseudokod implementacija

Algoritam se može izraziti kao (0- bazni niz):

procedure bubbleSort(A : list of sortable items )
   repeat     
     swapped = false
     for i = 1 to length(A) - 1 inclusive do:
       /* if this pair is out of order */
       if A[i-1] > A[i] then
         /* swap them and remember something changed */
         swap(A[i-1], A[i] )
         swapped = true
       end if
     end for
   until not swapped
end procedure

Da podsetimo, postoje bolji algoritmi za sortiranje kao što je kviksort koji se obično koriste, a većina programskih jezika ima ugrađenu funkciju u standardnoj biblioteci koja se može koristiti umesto da se implementira sopstveni algoritam za sortiranje.

Optimizacija bubble sorta

Bablsort algoritam se može lako opimizovati posmatranjem, ako se uoči da n-ti prolaz pronalazi n-ti najveći element i stavlja ga na njegovo mesto. Dakle, unutrašnja petlja može da se izbegne gledajući poslednjih n-1 elemenata kada radi za n-ti put:

procedure bubbleSort(A : list of sortable items )
    n = length(A)
    repeat
       swapped = false
       for i = 1 to n-1 inclusive do
          if A[i-1] > A[i] then
             swap(A[i-1], A[i])
             swapped = true
          end if
       end for
       n = n - 1
    until not swapped
end procedure

Uopšteno, može se desiti da se više od jednog elementa nalazi u završnoj poziciji u jednom prolazu. Konkretno, posle svakog prolaza, svi elementi do poslednje zamene su sortirani i ne treba ih ponovo proveravati. To nam omogućava da se presoči mnogo elemenata, što dovodi do u najgorem slučaju 50% poboljšanja i dodaje malo složenosti, jer novi kod podvodi „zamenljiva” promenljiva:

Da bi se ovo postiglo u pseudokodu pišemo sledeće:

procedure bubbleSort(A : list of sortable items )
    n = length(A)
    repeat
       newn = 0
       for i = 1 to n-1 inclusive do
          if A[i-1] > A[i] then
             swap(A[i-1], A[i])
             newn = i
          end if
       end for
       n = newn
    until n = 0
end procedure

Alternativne modifikacije, kao što je koktel sortiranje metoda pokušaji su da se poboljša bubble sort zadržavajući istu ideju (više puta se prede elementi i zamena susednih elemenata)

U praksi

Bablsort, algoritam za sortiranje koji stalno prolazi kroz niz, zamenjuje mesta elementima dok se ne pojave u ispravnom redosledu. Treba zapaziti da se prvo sortiraju najveći elementi, a zatim manji.

Iako je bablsort jedan od najjednostavnijih algoritama za sortiranje potrebno je razumeti i njegovu primenu. Njegova složenost O(n²) znači da se njegova efikasnost smanjuje dramatično na nizovima koji imaju veći broj elemenata. Čak i među jednostavnim O(n²) algoritmima, algoritmi poput sortiranja umetanjem su znatno efikasniji.

Zbog svoje jednostavnosti, bablsort se često koristi da se uvede koncept algoritama ili algoritam za sortiranje na uvodnim predavanjima studentima informatika. Međutim, neki istraživači kao što je Oven Astračan su otišli predaleko omalovažavajući bablsort i njegovu popularnost u obrazovanju informatičara preporučujući da se više i ne uči.

The Jargon file, čiji je poznati naziv glupi sort "the archetypical [sic] perversely awful algorithm", takođe naziva bablsort generički loš algoritam. Donald Knut u svojoj čuvenoj knjizi Umetnost računarskog programiranja zaključio je da se Bablsort nema po čemu preporučiti osim po privlačnom imenu i činjenici da ne ispoljava neke od zanimljivih teorijskih problema o kojim je on tada govorio.

Bablsort je asimptotski ekvivalentan sortiranju umetanjem po vremenu izvršavanja u najgorem slučaju, ali ova dva algoritma se veoma razlikuju po broju potrebnih zamena (svapova). Eksperimentalni rezultati kao što su oni od Astračana su takođe pokazali da sortiranje umetanjem radi znatno bolje čak i na slučajnim listama. Iz tih razloga mnogi moderni udžbenici izbegavaju korišćenje algoritma bablsorta u korist sortiranja umetanjem.

Bablsort takođe slabo komunicira sa modernim CPU hardverom. To zahteva najmanje duplo više pisanja nego kod insertion sorta, duplo vise keša, više filijala. Eksperimenti za Astračan sortiranje stringova u Javi pokazuje da algoritam mehura može da bude oko 5 puta sporiji od algoritma sa umetanjem i 40% sporiji od selekcionog sortiranja.

U kompjuterskoj grafici je popularan zbog njegove sposobnosti da otkrije veoma malu grešku (kao zamenu samo dva elementa) u skorosortiranim nizovima i popraviti je sa linearnom složenošću (2n).

Varijacije

• Sortiranje "par-nepar" je paralelna verzija bablsorta, za sisteme razmene poruka.
• Koktel sortiranje je paralelna verzija bablsorta.
• U nekim slučajevima, sortiranje se vrši sa desna na levo (u suprotnom smeru) koji je pogodniji za delimično sortirane nizove, odnosno nizove sa nesortiranim elementima na kraju.

Pogrešan naziv

Bablsort se pogrešno naziva potapajuće sortiranje. Potapajuće sortiranje je ispravan pseudonim za sortiranje sa umetanjem. Ova greška je uglavnom nastala kad je Nacionoalni institut za standarde i tehnologiju naveo taj pseudonim za bablsort. U knjizi Donalda Knuta „Umetnost kompjuterskog programiranja“, tom 3: sortiranja i pretrage, on navodi u odeljku 5.2.1 „sortiranje metodom umetanja rešava problem na svom pravom nivou“.

Literatura

• Knuth, Donald (1997). The Art of Computer Programming. Volume 3: Sorting and Searching, Third Edition. Addison-Wesley. стр. 106-110. ISBN 978-0-201-89685-5.  of section 5.2.2: Sorting by Exchanging.
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). Introduction to Algorithms. Second Edition. MIT Press and McGraw-Hill. ISBN 978-0-262-03293-3.  Problem 2-2, pp. 38.
• Sorting in the Presence of Branch Prediction and Caches
• Horowitz, Ellis; Sahni, Sartaj; Susan Anderson-Freed (2008). Fundamentals of Data Structures. ISBN 978-81-7371-605-8. 
• Алгоритми и структуре података - Мило Томашевић
• Увод у програмирање - Милан Шкарић

Spoljašnje veze

• „Bubble Sort - Engleska Wikipedija”. 
• „Bubble Sort implemented in 34 languages”. Архивирано из оригинала 22. 05. 2013. г. Приступљено 30. 05. 2013. 
• Toptal. „Animated Sorting Algorithms: Bubble Sort”.  – graphical demonstration and discussion of bubble sort
• „Lafore's Bubble Sort”. Архивирано из оригинала 19. 01. 2008. г. Приступљено 30. 05. 2013.  (Java applet animation)