Sortiranje mehurom — разлика између измена
Садржај обрисан Садржај додат
м Renamed template |
|||
Ред 1:
{{Infobox Algorithm
|class=[[Алгоритам сортирања]]
|image=[[Датотека:Bubblesort-edited-color.svg|
|data=[[Array data structure|Низ]]
|best-time= <math>O(n)</math>
|average-time= <math>O(n^2)</math>
|time=<math>O(n^2)</math>
|space=<math>O(1)</math>
|optimal=No
}}
'''Баблсорт''' је [[алгоритам]] који се користи ѕа сортирање низа. Алгоритам ради тако што упоређује свака два суседна члана низа и замењује им места ако су чланови низа у погрешном редоследу. Пролазимо кроз низ елемената све док се не изврши ниједна замена тј. елементи су сортирани у одговарајућем поретку (растућем или опадајућем). Назив је добио јер после прве итерације кроз низ највећи елемент се налази на највећој позицији у низу тј. на десној страни низа. Алгоритам је веома лак за имплементацију у свим програмским језицима али је веома непрактичан и спор чак и када га упоредимо са алгоритмом као што је [[Sortiranje umetanjem|сортирање уметањем]].<ref name="Knuth">{{cite book|first=Knuth|quote=Имеплементирао баблсорт алгоритам}}</ref> Алгоритам ради добро за низ који има мали број елемената или који је полусортиран тј. само одређени број елемената је на неправилним позицијама.
== Анализа алгоритма ==
[[Датотека:Bubble-sort-example-300px.gif|300px|thumb|right|Пример баблсорт алгоритма.]]
Баблсорт има најгору и просечну комплексност ''[[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''). И ово је најбоља комплексност алгоритма.
== Пример ==
Корисник уноси низ бројева 10 4 55 21 6 морамо да сортирамо овај низ бројева у растућем поретку користећи баблсорт.
Прва итерација:
( '''10''' '''4''' 55 21 6 ) <math>\to</math> ( '''4''' '''10''' 55 21 6 ), Овде алгоритам упоређује прва два суседна елемента низа и врши замену јер је 10 > 4.
( 4 '''10''' '''55''' 21 6 ) <math>\to</math> ( 4 '''10''' '''55''' 21 6 ), Овде не вршимо замену јер је 10 < 55
( 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
Друга итерација:
(
(
( 4 10 '''21''' '''6''' 55 ) <math>\to</math> ( 4 10 '''6''' '''21''' 55 ), Овде вршимо замену јер је 21 > 6
( 4 10 6 '''
Друга итерација:
(
( 4 '''10''' '''6''' 21 55 ) <math>\to</math> ( 4 '''6''' '''10''' 21 55 ), Овде вршимо замену јер је 10 > 6
( 4 6 '''10''' '''21''' 55 ) <math>\to</math> ( 4 6 '''10''' '''21''' 55 ), Овде не вршимо замену јер је 10 < 21
( 4 6 10 '''
== Имплементација алгоритма ==
Ово је имплементација алгоритма у програмском језику С.
include<stdio.h><ref name="Псеудокод">{{cite book|first=Милан|last=Шкарић|title=Увод у програмирање|publisher=Микро књига|location=Београд|quote=Имплементација баблсор алгоритма}}</ref>
include<conio.h>
void main() {
int arr[30], num, i;
printf("\nУнесите број елемената низа :");
scanf("%d", &num);
printf("\nУнесите елементе низа :");
for (i = 0; i < num; i++)
scanf("%d", &arr[i]);
bubble_sort(arr, num);
getch();
}
Ово је функција у којој смо имплеметирали бублсорт.
void bubble_sort(int iarr[], int num) {
int i, j, k, temp;
printf("\nНе сортирани низ:");
for (k = 0; k < num; k++) {
printf("%5d", iarr[k]);
}
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 овде]
# Алгоритми и структуре података - Мило Томашевић
# Увод у програмирање - Милан Шкарић
[[Категорија:Алгоритми]]
[[Категорија:Алгоритми сортирања]]
[[Категорија:
|