Sortiranje mehurom — разлика између измена
Садржај обрисан Садржај додат
м Разне исправке |
м Уклањање сувишних унутрашњих веза |
||
Ред 7:
Bubble sort ima najgoru složenost ''[[big o notation|О]]''(''n''<sup>2</sup>), 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''<sup>2</sup>), kao što je [[sortiranje umetanjem|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 [[sortiranje umetanjem|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
=== Zečevi i kornjače ===
Ред 103:
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">
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]].
| |||