Википедија

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

Интерактиван преглед историје
← Старија изменаНовија измена →
Садржај обрисан Садржај додат
ВизуелноВикитекст
Autobot (разговор | доприноси)
1.572.075 измена
м Бот: исправљена преусмерења
Autobot (разговор | доприноси)
1.572.075 измена
м Разне исправке
Ред 21:
 
 
'''Prvi prolazak:'''<br />
 
('''5''' '''1''' 4 2 8 ) <math>\to</math> ('''1''' '''5''' 4 2 8 ), Algoritam upoređuje prva dva elementa i zamenjuje 1 i 5 , 5 > 1.<br />▼
(1 '''5''' '''41''' 4 2 8 ) <math>\to</math> (1 '''41''' '''5''' 4 2 8 ), zamenaAlgoritam poštoupoređuje jeprva 5dva >elementa 4i <brzamenjuje 1 i 5 , 5 /> 1.
 
(1 4 '''5''' '''2''' 8 ) <math>\to</math> (1 4 '''2''' '''5''' 8 ), zamena pošto je 5 > 2 <br />▼
(1 4 2 '''5''' '''84''' 2 8 ) <math>\to</math> (1 4 2 '''54''' '''85''' 2 8 ), Sada,zamena pošto suje ovi elementi već sortirani (85 > 5),4 algoritam ih neće zameniti.<br />
 
'''Drugi prolazak:'''<br />▼
(1 4 '''15''' '''42''' 2 5 8 ) <math>\to</math> (1 4 '''12''' '''45''' 2 5 8 )<br, zamena pošto je 5 /> 2
 
(1 '''4''' '''2''' 5 8 ) <math>\to</math> (1 '''2''' '''4''' 5 8 ), zamena pošto je 4 > 2 <br />▼
(1 4 2 '''45''' '''58''' 8 ) <math>\to</math> (1 4 2 '''45''' '''58''' ), Sada, pošto su ovi elementi već sortirani (8 > 5)<br, />algoritam ih neće zameniti.
 
(1 2 4 '''5''' '''8''' ) <math>\to</math> (1 2 4 '''5''' '''8''' )<br />▼
▲'''Drugi prolazak:'''<br />
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'''.<br />▼
 
'''Treći prolazak:'''<br />▼
('''1''' '''24''' 42 5 8 ) <math>\to</math> ('''1''' '''24''' 42 5 8 )<br />
 
(1 '''2''' '''4''' 5 8 ) <math>\to</math> (1 '''2''' '''4''' 5 8 )<br />▼
(1 2 '''4''' '''52''' 5 8 ) <math>\to</math> (1 2 '''42''' '''54''' 5 8 )<br, zamena pošto je 4 /> 2
 
▲(1 42 '''54''' '''25''' 8 ) <math>\to</math> (1 42 '''24''' '''5''' 8 ), zamena pošto je 5 > 2 <br />
 
▲(1 2 4 '''5''' '''8''' ) <math>\to</math> (1 2 4 '''5''' '''8''' )<br />
 
▲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'''.<br />
 
▲'''Treći prolazak:'''<br />
 
▲('''51''' '''12''' 4 25 8 ) <math>\to</math> ('''1''' '''52''' 4 25 8 ), Algoritam upoređuje prva dva elementa i zamenjuje 1 i 5 , 5 > 1.<br />
 
▲(1 '''42''' '''24''' 5 8 ) <math>\to</math> (1 '''2''' '''4''' 5 8 ), zamena pošto je 4 > 2 <br />
 
▲(1 2 '''24''' '''45''' 5 8 ) <math>\to</math> (1 2 '''24''' '''45''' 5 8 )<br />
 
(1 2 4 '''5''' '''8''' ) <math>\to</math> (1 2 4 '''5''' '''8''' )
 
Линија 105 ⟶ 120:
Zbog svoje jednostavnosti, bubble sort 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]] 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.<ref name="Astrachan2003" />
 
The [[Jargon file]], čiji je poznati naziv [[глупи сорт|bogosort]] "the archetypical [sic] perversely awful algorithm", takođe naziva bubble sort '''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 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.<ref name="Knuth">Donald Knuth. ''[[The Art of Computer Programming]]'', Volume 3: ''Sorting and Searching'', Second Edition. Addison-Wesley. {{page|year=1998. ISBN |isbn=978-0-201-89685-5. стр. |pages=106-110.}} of section 5.2.2: Sorting by Exchanging.</ref>
 
Bubble sort je asimptotski ekvivalentan [[sortiranje umetanjem|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 [[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 sorta u korist [[sortiranje umetanjem|insertion sorta]].
Линија 127 ⟶ 142:
 
== Literatura ==
* {{cite book|author=[[Donald Knut]]h. ''|title=The Art of Computer Programming'', |location=Volume 3: |publisher=''Sorting and Searching'', Third Edition. Addison-Wesley. |year=1997. ISBN |isbn=978-0-201-89685-5. стр. |pages=106-110.}} of section 5.2.2: Sorting by Exchanging.
* {{cite book|author=[[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Роналд Лин Ривест|Ronald L. Rivest]], and [[Clifford Stein]]. ''|title=[[Introduction to Algorithms]]'', |location=|publisher=Second Edition. MIT Press and McGraw-Hill. |year=2001. ISBN |isbn=978-0-262-03293-3.|pages=}} Problem 2-2, pg.38.
* [https://www.cs.tcd.ie/publications/tech-reports/reports.05/TCD-CS-2005-57.pdf Sorting in the Presence of Branch Prediction and Caches]
* {{cite book|author=Ellis Horowitz, [[Sartaj Sahni]] and Susan Anderson-Freed|title=Fundamentals of Data Structures|publisher=|location=|year=|isbn=978-81-7371-605-8|pages=}}
Линија 136 ⟶ 151:
* {{cite web | url=http://en.wikipedia.org/wiki/Bubble_sort| title= Bubble Sort - Engleska Wikipedija}}
* {{cite web | url=http://codecodex.com/wiki/Bubble_sort | title= Bubble Sort implemented in 34 languages}}
* {{cite web | url=http://www.sorting-algorithms.com/bubble-sort |title = Animated Sorting Algorithms: Bubble Sort | authorlast=Martin|first= David R. Martin}} – -{graphical demonstration and discussion of bubble sort}-
* {{cite web | url= http://lecture.ecc.u-tokyo.ac.jp/~ueda/JavaApplet/BubbleSort.html |title= Lafore's Bubble Sort}} (Java applet animation)
 
Преузето из „https://sr.wikipedia.org/wiki/Sortiranje_mehurom”