Sortiranje mehurom — разлика између измена

|image=[[Датотека:Bubblesort-edited-color.svg|frame|SortiranjeVizuelna mehurompredstava bablsort algoritma<br />|thumb|center]]

[[Датотека:Bubble-sort-example-300px.gif|300px|мини|right|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.]]

=== PERFORMANSEPerformanse ===

Bubble sortBablsort ima najgoru složenost ''[[big o notation|О]]''(-{''n''}-²), gde je -{''n''}- broj elemenata koji se sortiraju. Postoji mnogo algoritama za sortiranje koji imaju znatno bolju složenost -{''O''(''n''&nbsp;log&nbsp;''n'')}-. Čak i drugi algoritimi složenosti -{''О''(''n''²)}-, kao što je [[sortiranje umetanjem|insertion sort]], imaju tendenciju da imaju bojebolje performanse od bubble sortabablsorta. Dakle, bubblesortiranje sortmehurom nije praktičan algoritam za sortiranje kada je -{''n''}- veliko.

Jedina značajna prednost bubble sortabablsorta za razliku od drugih implementacija, čak i [[квиксорт|quicksortakviksort]]a, ali ne [[sortiranje umetanjem|insertionsortiranja sortaumetanjem]], je sposobnost da otkrije da je sortiran niz efikasno ugrađen u algoritam. Složenost bubble sortabablsorta 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]])

Pozicije elemenata u bubble sortubablsortu 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 daseda se eliminišu kornjače kako bi se poboljšala brzina bubble sortabablsorta. [[CocktailKoktel sortiranje|Koktelsort]] sort je dvosmerni bubble sortbablsort koji idiide 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²)}-]]''. [[Comb sort|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 [[квиксорт|quicksortkviksort]].

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

Da podsetimo, postoje bolji algoritmi za sortiranje kao što je [[квиксорт|quicksortkviksort]] 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.

Bubble sortBablsort algoritam se može lako opimizovati posmatranjem, ako opazimose 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:

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”„zamenljiva” promenljiva:

Alternativne modifikacije, kao što je [[cocktailkoktel shaker sortsortiranje]] 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)

[[Датотека:Bubble sort animation.gif|мини|right|280px|Bubble sortBablsort, 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 sortbablsort 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 medjumeđu jednostavnim -{''O(n²)''}- algoritmima, algoritmi poput [[insertionsortiranje umetanjem |sortiranja sortaumetanjem]] su znatno efikasniji.

Zbog svoje jednostavnosti, bubble sortbablsort se često koristi da se uvede koncept algoritama ili algoritam za sortiranje na uvodnim predavanjima studentima [[informatike|informatika]]. Međutim, neki istraživači kao što je [[Oven Astrachan |Oven Astračan]] su otišli predaleko omalovažavajući bubble sortbablsort i njegovu popularnost u obrazovanju informatičara preporučujući da se više i ne uči.<ref name="Astrachan2003" />

The [[Jargon file]], čiji je poznati naziv [[глупиglupi сорт|bogosortsort]] -{"the archetypical [sic] perversely awful algorithm"}-, takođe naziva bubble sortbablsort '''generički loš algoritam'''.<ref>[http://www.jargon.net/jargonfile/b/bogo-sort.html jargon, node: bogo-sort<!-- Bot generated title -->]</ref> [[Donald Knut]]h u svojoj čuvenoj knjizi ''[[Umetnost računarskog programiranja]]'' zaključio je da se Bubble sortBablsort nema po čemu preporučiti osim po privlacnomprivlačnom imenu i činjenici da voidne oispoljava neke nekihod zanimljivih teorijskih probemaproblema o kojim je on tada govorio.<ref name="Knuth">Donald Knuth. ''[[The Art of Computer Programming]]'', Volume 3: ''Sorting and Searching'', Second Edition. Addison-Wesley. {{page|year=1998|isbn=978-0-201-89685-5|pages=106-110}} of section 5.2.2: Sorting by Exchanging.</ref>

Bubble sortBablsort je asimptotski ekvivalentan [[sortiranje umetanjem|insertionsortiranju sortuumetanjem]] 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 AstrachanaAstračana su takođe pokazali da [[sortiranje umetanjem|insertion sort]] radi znatno bolje čak i na slučajnim listama. Iz tih razloga mnogi moderni udžbenici izbegavaju korišćenje algoritma bubble sortabablsorta u korist [[sortiranjesortiranja umetanjem|insertion sorta]].

Bubble sortBablsort 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 AstrachanAstračan sortiranje stringova u Javi pokazuje da bubblealgoritam mehura može da bude oko 5 puta sporiji od [[insertonalgoritma sorta]]sa umetanjem i 40% sporiji od [[сортирање селекцијом|selectionselekcionog sortasortiranja]].<ref name="Astrachan2003">Owen Astrachan. Bubble Sort: An Archaeological Algorithmic Analysis. SIGCSE 2003 Hannan Akhtar . [http://www.cs.duke.edu/~ola/papers/bubble.pdf (pdf)]</ref>

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}-).

* [[OddSortiranje "par-even sortnepar"]] je paralelna verzija bubble sortabablsorta, za messagesisteme passingrazmene systemsporuka.

* [[CocktailKoktel sortsortiranje]] je paralelna verzija bubble sortabablsorta.

Bubble sortBablsort se pogrešno naziva sinkingpotapajuće sortsortiranje. SinkingPotapajuće sortsortiranje je ispravan pseudonim za insertionsortiranje sa sortumetanjem. Ova greška je uglavnom poštonastala kad je Nacionoalni institut za standarde i tehnologiju naveo sinking sort kaotaj pseudonim za bubble sortbablsort. U knjizi [http://xlinux.nist.gov/dads/HTML/bubblesort.html] DonaldDonalda KnuthKnuta „Umetnost kompjuterskog programiranja“, tom3tom 3: ''sortiranja i pretrage'', Donalon Knuth kaženavodi u odeljku 5.2.1 „ sortiranje„sortiranje metodom insertion sortumetanja rešava problem 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.

* {{cite book|author=[[Thomas H.Donald Cormen]],Knuth [[Charles E. Leiserson]], [[Роналд Лин Ривест|Ronaldtitle=The L.Art Rivest]],of andComputer [[Clifford Stein]]Programming|titlelocation=[[IntroductionVolume to Algorithms]]|location=3|publisher=Second''Sorting Edition.and MITSearching'', PressThird andEdition. McGrawAddison-HillWesley|year=20011997|isbn=978-0-262201-0329389685-35|pages=106-110}} Problemof section 5.2-.2,: pg.38Sorting by Exchanging.

* {{cite book|author=Ellis Horowitz, [[|author2= Sartaj Sahni]] and|author3= Susan Anderson-Freed |title=Fundamentals of Data Structures |publisher=|location= |year=|isbn=978-81-7371-605-8|pages=}}