Sortiranje mehurom

Из Википедије, слободне енциклопедије

Sortiranje mehurom (engl. Bubble sort), ponekad pogrešno nazivan sinking sort, je jednostavan algoritam za sortiranje koji radi tako što više puta prolazi kroz niz koji treba da bude sortiran i upoređuje se svaki par susednih eleenata. Elementi zamenjuju mesta ako su napisani pogresnim redom. Prolaz kroz niz se ponavlja se dok se ne izvrše sve potrebne zamene, što ukazuje da je niz sortiran. Algoritam je dobio ime zbog načina na koji najmanji elemenat „bubble“ dolazi na početak niza. Pošto se samo porede elementi, ovo je komparativno sortiranje. Iako je ovo jednostavan algoritam, većina drugih algoritama za sortiranje su efikasniji za velike nizove.

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[уреди]

Bubble sort ima najgoru složenost О(n2), 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 О(n2), kao što je insertion sort, imaju tendenciju da imaju boje performanse od bubble sorta. Dakle, bubble sort nije praktičan algoritam za sortiranje kada je n veliko.

Jedina značajna prednost bubble sorta za razliku od drugih implementacija, čak i quicksorta, ali ne insertion sorta, je sposobnost da otkrije da je sortiran niz efikasno ugrađen u algoritam. Složenost bubble sorta 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 bubble sortu 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 dase eliminišu kornjače kako bi se poboljšala brzina bubble sorta. Cocktail sort je dvosmerni bubble sort koji idi 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(n2). Comb sort 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 quicksort.

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 bubble sort-a. 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 quicksort 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[уреди]

Bubble sort algoritam se može lako opimizovati posmatranjem ako opazimo 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 cocktail shaker sort 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[уреди]

Bubble sort, 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 bubble sort jedan od najjednostavnijih algoritama za sortiranje potrebno je razumeti i njegovu primenu. Njegova složenost O(n2) znači da se njegova efikasnost smanjuje dramatično na nizovima koji imaju veći broj elemenata. Čak i medju jednostavnim O(n2) algoritmima, algoritmi poput insertion sorta su znatno efikasniji.

Zbog svoje jednostavnosti, bubble sort 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 Astrachan su otišli predaleko omalovažavajući bubble sort i njegovu popularnost u obrazovanju informatičara preporučujući da se više i ne uči.[1]

The Jargon file, čiji je poznati naziv bogosort "the archetypical [sic] perversely awful algorithm", takođe naziva bubble sort generički loš algoritam.[2] Donald Knuth u svojoj čuvenoj knjizi Umetnost računarskog programiranja zaključio je da se Bubble sort nema po čemu preporučiti osim po privlacnom imenu i činjenici da void o nekih zanimljivih teorijskih probema o kojim je on tada govorio.[3]

Bubble sort je asimptotski ekvivalentan insertion sortu 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 Astrachana su takođe pokazali da insertion sort radi znatno bolje čak i na slučajnim listama. Iz tih razloga mnogi moderni udžbenici izbegavaju korišćenje algoritma bubble sorta u korist insertion sorta.

Bubble sort 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 Astrachan sortiranje stringova u Javi pokazuje da bubble može da bude oko 5 puta sporiji od inserton sorta i 40% sporiji od selection sorta.[1]

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[уреди]

  • Odd-even sort je paralelna verzija bubble sorta, za message passing systems.
  • Cocktail sort je paralelna verzija bubble sorta
  • 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[уреди]

Bubble sort se pogrešno naziva sinking sort. Sinking sort je ispravan pseudonim za insertion sort. Ova greška je uglavnom pošto je Nacionoalni institut za standarde i tehnologiju naveo sinking sort kao pseudonim za bubble sort. U knjizi [1] Donald Knuth „Umetnost kompjuterskog programiranja“, tom3: sortiranja i pretrage, Donal Knuth kaže u odeljku 5.2.1 „ sortiranje metodom insertion sort rešava na svom pravom nivou“. Ovaj metod je često nazivan sinking sort. Pored toga, veće vrednosti se mogu smatrati kao teže i zbog toga one postepeno „tonu“ na dno liste, što je dovelo do toga da se pogrešno upotrebljava ovaj naziv.

Da pojasnimo, možemo posmatrati ponašanje 2 algoritama. U bubble sortu, veći mehurići (više vrednosti) će isplivati zamenjujući manje mehuriće (niže vrednosti). Insertion sort, sa druge strane, potapa svaku sledeću vrednost do svog mesta u sortiranom delu niza.

Reference[уреди]

  1. ^ а б Owen Astrachan. Bubble Sort: An Archaeological Algorithmic Analysis. SIGCSE 2003 Hannan Akhtar . (pdf)
  2. ^ jargon, node: bogo-sort
  3. ^ Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1998. ISBN 0-201-89685-0. Pages 106-110 of section 5.2.2: Sorting by Exchanging.

Literatura[уреди]

Spoljašnje veze[уреди]

Викиостава
Викимедијина остава има још мултимедијалних датотека везаних за: Sortiranje mehurom