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

Садржај обрисан Садржај додат
м Renamed template
Ред 1:
{{Infobox Algorithm
{{Neprovereni seminarski}}
|class=[[Алгоритам сортирања]]
{{спајање|Баблсорт}}
|image=[[Датотека:Bubblesort-edited-color.svg|frame|SortiranjeВизуелна mehuromпредстава баблсорт алгоритма<br />|thumb|center]]
|data=[[Array data structure|Низ]]
'''Sortiranje mehurom''' ({{jez-eng-lat|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 elemenata. 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.
|best-time= <math>O(n)</math>
== Analiza ==
|average-time= <math>O(n^2)</math>
[[Датотека: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.]]
|time=<math>O(n^2)</math>
|space=<math>O(1)</math>
|optimal=No
}}
'''Баблсорт''' је [[алгоритам]] који се користи ѕа сортирање низа. Алгоритам ради тако што упоређује свака два суседна члана низа и замењује им места ако су чланови низа у погрешном редоследу. Пролазимо кроз низ елемената све док се не изврши ниједна замена тј. елементи су сортирани у одговарајућем поретку (растућем или опадајућем). Назив је добио јер после прве итерације кроз низ највећи елемент се налази на највећој позицији у низу тј. на десној страни низа. Алгоритам је веома лак за имплементацију у свим програмским језицима али је веома непрактичан и спор чак и када га упоредимо са алгоритмом као што је [[Sortiranje umetanjem|сортирање уметањем]].<ref name="Knuth">{{cite book|first=Knuth|quote=Имеплементирао баблсорт алгоритам}}</ref> Алгоритам ради добро за низ који има мали број елемената или који је полусортиран тј. само одређени број елемената је на неправилним позицијама.
 
== Анализа алгоритма ==
=== PERFORMANSE ===
[[Датотека:Bubble-sort-example-300px.gif|300px|thumb|right|Пример баблсорт алгоритма.]]
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''&nbsp;log&nbsp;''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.
 
Баблсорт има најгору и просечну комплексност ''[[big o notation|О]]''(''n''<sup>2</sup>)<ref name="Нотација">{{cite book|first=Алгоритам|quote=Означава комплексност алгоритама}}</ref> где је n број ставки у низу које треба да се сортирају. Чак и алгоритми који имају комплексност ''[[big o notation|О]]''(''n''<sup>2</sup>)као сто је [[Sortiranje umetanjem|сортирање уметањем]] има бољу перформансу од баблсорта. Баблсорт је једино добар кад n(број ставки у низу) није велики. Предност овог алгоритма у односу на све остале алгоритме са бољом перформансом је што без проблема може да одреди да ли је низ сортиран и тада је сложеност ''[[big o notation|О]]''(''n''). И ово је најбоља комплексност алгоритма.
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 insertion sort ima ovaj mehanizam, već i bolje radi na nizu koji je znatno sortiran (mali broj [[inverzija]])
 
== Пример ==
=== Zečevi i kornjače ===
Корисник уноси низ бројева 10 4 55 21 6 морамо да сортирамо овај низ бројева у растућем поретку користећи баблсорт.
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(n<sup>2</sup>)]]''. [[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]].
 
( '''10''' '''4''' 55 21 6 ) <math>\to</math> ( '''4''' '''10''' 55 21 6 ), Овде алгоритам упоређује прва два суседна елемента низа и врши замену јер је 10 > 4.
=== Korak po korak primer ===
 
( 4 '''10''' '''55''' 21 6 ) <math>\to</math> ( 4 '''10''' '''55''' 21 6 ), Овде не вршимо замену јер је 10 < 55
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:
 
( 4 10 '''55''' '''21''' 6 ) <math>\to</math> ( 4 10 '''21''' '''55''' 6 ), Овде вршимо замену јер је 55 > 21
 
( 4 10 21 '''55''' '''6''' ) <math>\to</math> ( 4 10 21 '''6''' '''55''' ), Овде вршимо замену јер је 55 > 6
'''Prvi prolazak:'''
 
('''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.
 
Друга итерација:
(1 '''5''' '''4''' 2 8 ) <math>\to</math> (1 '''4''' '''5''' 2 8 ), zamena pošto je 5 > 4
 
(1 4 '''54''' '''210''' 821 6 55 ) <math>\to</math> (1 4 '''24''' '''510''' 855 21 6 ), zamenaОвде poštoне jeвршимо 5замену >јер је 4 < 210
 
(1 4 2 '''510''' '''821''' 6 55 ) <math>\to</math> (1 4 2 '''510''' '''821''' 6 55 ), Sada,Овде poštoне suвршимо oviзамену elementiјер većје sortirani10 (8 > 5), algoritam ih< neće21 zameniti.
 
( 4 10 '''21''' '''6''' 55 ) <math>\to</math> ( 4 10 '''6''' '''21''' 55 ), Овде вршимо замену јер је 21 > 6
'''Drugi prolazak:'''
 
( 4 10 6 '''121''' '''455''' 2 5 8 ) <math>\to</math> ( 4 10 21 '''16''' '''455''' 2), 5Овде 8не вршимо замену јер је 21 < 55 )
 
(1 '''4''' '''2''' 5 8 ) <math>\to</math> (1 '''2''' '''4''' 5 8 ), zamena pošto je 4 > 2
 
Друга итерација:
(1 2 '''4''' '''5''' 8 ) <math>\to</math> (1 2 '''4''' '''5''' 8 )
 
(1 2 4 '''54''' '''810''' 6 21 55 ) <math>\to</math> (1 2 4 '''54''' '''810''' 6 21 55 ), Овде не вршимо замену јер је 4 < 10
 
( 4 '''10''' '''6''' 21 55 ) <math>\to</math> ( 4 '''6''' '''10''' 21 55 ), Овде вршимо замену јер је 10 > 6
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'''.
 
( 4 6 '''10''' '''21''' 55 ) <math>\to</math> ( 4 6 '''10''' '''21''' 55 ), Овде не вршимо замену јер је 10 < 21
'''Treći prolazak:'''
 
( 4 6 10 '''121''' '''255''' 4 5 8 ) <math>\to</math> ( 4 6 10 '''121''' '''255''' 4), 5Овде 8не вршимо замену јер је 21 < 55 )
 
(1 '''2''' '''4''' 5 8 ) <math>\to</math> (1 '''2''' '''4''' 5 8 )
 
== Имплементација алгоритма ==
(1 2 '''4''' '''5''' 8 ) <math>\to</math> (1 2 '''4''' '''5''' 8 )
Ово је имплементација алгоритма у програмском језику С.
 
(1 2 4 '''5''' '''8''' ) <math>\to</math> (1 2 4 '''5''' '''8''' )
 
include<stdio.h><ref name="Псеудокод">{{cite book|first=Милан|last=Шкарић|title=Увод у програмирање|publisher=Микро књига|location=Београд|quote=Имплементација баблсор алгоритма}}</ref>
== Implementacija ==
=== Pseudokod implementacija ===
Algoritam se može izraziti kao (0- bazni niz):
<source lang="pli">
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
</source>
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.
 
include<conio.h>
=== 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:
 
void main() {
<source lang="pli">
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
</source>
 
int arr[30], num, i;
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:
 
printf("\nУнесите број елемената низа :");
 
scanf("%d", &num);
Da bi se ovo postiglo u [[pseudokod]]u pišemo sledeće:
<source lang="pli">
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
</source>
 
printf("\nУнесите елементе низа :");
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)
 
for (i = 0; i < num; i++)
== U praksi ==
[[Датотека:Bubble sort animation.gif|мини|right|280px|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(n<sup>2</sup>)]]'' znači da se njegova efikasnost smanjuje dramatično na nizovima koji imaju veći broj elemenata. Čak i medju jednostavnim ''O(n<sup>2</sup>)'' algoritmima, algoritmi poput [[insertion sorta]] su znatno efikasniji.
 
scanf("%d", &arr[i]);
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" />
 
bubble_sort(arr, num);
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=978-0-201-89685-5|pages=106-110}} of section 5.2.2: Sorting by Exchanging.</ref>
 
getch();
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]].
 
}
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]].<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).
 
== 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 [http://xlinux.nist.gov/dads/HTML/bubblesort.html] 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.
 
void bubble_sort(int iarr[], int num) {
== Reference ==
{{reflist}}
 
int i, j, k, temp;
== 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=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=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=}}
 
printf("\nНе сортирани низ:");
== Spoljašnje veze ==
 
{{Commonscat|Bubble sort}}
for (k = 0; k < num; k++) {
* {{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}}
printf("%5d", iarr[k]);
* {{cite web | url=http://www.sorting-algorithms.com/bubble-sort |title = Animated Sorting Algorithms: Bubble Sort |last=Martin|first=David R.}} – -{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)
}
 
for (i = 1; i < num; i++) {
 
for (j = 0; j < num - 1; j++) {
 
if (iarr[j] > iarr[j + 1]) {
 
temp = iarr[j];
 
iarr[j] = iarr[j + 1];
 
iarr[j + 1] = temp;
 
}
 
}
 
printf("\nПосле %d итерације : ", i);
 
for (k = 0; k < num; k++) {
 
printf("%5d", iarr[k]);
 
}
 
}
 
}
 
 
 
 
=== Резултат програма ===
 
 
Унесите број елемената низа :5
 
Унесите елементе :10 4 55 21 6
 
Несортиран низ : 10 4 55 21 6
 
После 1 итерације : 4 10 21 6 55
 
После 2 итерације : 4 10 6 21 55
 
После 3 итерације : 4 6 10 21 55
 
После 4 итерације : 4 6 10 21 55
 
== Слични алгоритми ==
Слични овом алгоритму је алгоритам [[Koktel sortiranje|коктел сортирање]] он ради на истом принципу као и баблсорт само сто у једној итерацији пролази кроз низ прво са леве па онда са десне стране.
== Референце ==
 
{{reflist}}
# Introductions to algorithms -Thomas H. Cormen,Charles E. Leiserson,Ronald L. Rivest,Clifford Stein, књигу можете погледати [http://bayanbox.ir/view/4177858657730907268/introduction-to-algorithms-3rd-edition.pdf овде]
# Алгоритми и структуре података - Мило Томашевић
# Увод у програмирање - Милан Шкарић
 
[[Категорија:Алгоритми]]
[[Категорија:Алгоритми сортирања]]
[[Категорија:Сортирање поређењемНизови]]
[[Категорија:Стабилно сортирање]]