Википедија

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

Интерактиван преглед историје
← Старија изменаНовија измена →
Садржај обрисан Садржај додат
ВизуелноВикитекст
Нема описа измене
Autobot (разговор | доприноси)
1.572.075 измена
м Разне исправке; козметичке измене
Ред 1:
Баблсорт је [[Алгоритам|алгоритам]] који се користи ѕа сортирање низа.Алгоритам ради тако сто упоређује свака два суседна члана низа и зaмeњујезамењује им места ако су чланови низа у погрешном редоследу.Пролазимо кроз низ елемената све док се не изврши ниједна замена тј. елементи су сортирани у одговарајућем поретку(растућем или опадајућем). Назив је добио јер после прве итерације кроз низ највећи елемент се налази на највећој позицији у низу тј. на десној страни низа.Алгоритам је веома лак за имплементацију у свим програмским језицима али веома непрактичан и спор чак и када га упоредимо са алгоритмом као сто је [[Sortiranje umetanjem|сортирање уметањем]].Алгоритам ради добро за низ који има мали број елемената или који је полусортиран тј. само одређени број елемената је на неправилним позицијама.
 
== Анализа алгоритма ==
Баблсорт има нијгору и просечну комплексност ''[[big o notation|О]]''(''n''<sup>2</sup>) где је n број ставки у низу које треба да се сортирају.Чак и алгоритми који имају комплексност ''[[big o notation|О]]''(''n''<sup>2</sup>)као сто је [[Sortiranje umetanjem|сортирање уметањем]] има бољу перформансу од баблсорта.Баблсорт је једино добар кад n(број ставки у низу) није велики.Предност овог алгоритма у односу на све остале алгоритме са бољом перформансом је што без проблема може да одреди да ли је низ сортиран и тада је сложеност ''[[big o notation|О]]''(''n'').И ово је најбоља комплексност алгоритма.
== Пример ==
Корисник уноси низ бројева 10 4 55 21 6 морамо да сортирамо овај низ бројева у растућем поретку користећи баблсорт.<br />
Прва итерација:<br />
( '''10''' '''4''' 55 21 6 ) <math>\to</math> ( '''4''' '''10''' 55 21 6 ), Овде алгоритам упоређује прва два суседна елемента низа и врши замену јер је 10 > 4.<br />
( 4 '''10''' '''55''' 21 6 ) <math>\to</math> ( 4 '''10''' '''55''' 21 6 ), Овде не вршимо замену јер је 10 < 55 <br />
( 4 10 '''55''' '''21''' 6 ) <math>\to</math> ( 4 10 '''21''' '''55''' 6 ), Овде вршимо замену јер је 55 > 21 <br />
( 4 10 21 '''55''' '''6''' ) <math>\to</math> ( 4 10 21 '''6''' '''55''' ), Овде вршимо замену јер је 55 > 6 <br />
 
ДругаПрва итерација:<br />
 
( '''4''' '''10''' 21 6 55 ) <math>\to</math> ( '''4''' '''10''' 55 21 6 ), Овде не вршимо замену јер је 4 < 10 <br />
( 4 '''10''' '''214''' 6 55 21 6 ) <math>\to</math> ( 4 '''104''' '''2110''' 6 55 21 6 ), Овде неалгоритам вршимоупоређује прва два суседна елемента низа и врши замену јер је 10 <> 21 <br />4.
 
( 4 10 '''21''' '''6''' 55 ) <math>\to</math> ( 4 10 '''6''' '''21''' 55 ), Овде вршимо замену јер је 21 > 6 <br />
( 4 10 6 '''2110''' '''55''' 21 6 ) <math>\to</math> ( 4 10 21 '''610''' '''55''' 21 6 ), Овде не вршимо замену јер је 2110 < 55 <br />
 
( 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''' 55 21 6 ), Овде не вршимо замену јер је 4 < 10
 
( 4 '''10''' '''21''' 6 55 ) <math>\to</math> ( 4 '''10''' '''21''' 6 55 ), Овде не вршимо замену јер је 10 < 21
 
( 4 10 '''21''' '''6''' 55 ) <math>\to</math> ( 4 10 '''6''' '''21''' 55 ), Овде вршимо замену јер је 21 > 6
 
( 4 10 6 '''21''' '''55''' ) <math>\to</math> ( 4 10 21 '''6''' '''55''' ), Овде не вршимо замену јер је 21 < 55
 
 
Друга итерација:
 
( '''4''' '''10''' 6 21 55 ) <math>\to</math> ( '''4''' '''10''' 6 21 55 ), Овде не вршимо замену јер је 4 < 10
 
( 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 '''21''' '''55''' ) <math>\to</math> ( 4 6 10 '''21''' '''55''' ), Овде не вршимо замену јер је 21 < 55
 
Друга итерација:<br />
( '''4''' '''10''' 6 21 55 ) <math>\to</math> ( '''4''' '''10''' 6 21 55 ), Овде не вршимо замену јер је 4 < 10 <br />
( 4 '''10''' '''6''' 21 55 ) <math>\to</math> ( 4 '''6''' '''10''' 21 55 ), Овде вршимо замену јер је 10 > 6 <br />
( 4 6 '''10''' '''21''' 55 ) <math>\to</math> ( 4 6 '''10''' '''21''' 55 ), Овде не вршимо замену јер је 10 < 21 <br />
( 4 6 10 '''21''' '''55''' ) <math>\to</math> ( 4 6 10 '''21''' '''55''' ), Овде не вршимо замену јер је 21 < 55 <br />
 
== Имплементација алгоритма ==
Ово је имплементација алгоритма у програмском језику С.<br />
 
 
include<stdio.h>
 
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();
 
}
 
 
 
include<stdio.h><br />
include<conio.h><br />
void main() {<br />
int arr[30], num, i;<br />
printf("\nУнесите број елемената низа :");<br />
scanf("%d", &num);<br />
printf("\nУнесите елементе низа :");<br />
for (i = 0; i < num; i++)<br />
scanf("%d", &arr[i]);<br />
bubble_sort(arr, num);<br />
getch();<br />
}<br />
<br />
Ово је функција у којој смо имплеметирали бублсорт.
<br />
void bubble_sort(int iarr[], int num) {<br />
int i, j, k, temp;<br />
printf("\nНе сортирани низ:");<br />
for (k = 0; k < num; k++) {<br />
printf("%5d", iarr[k]);<br />
}<br />
for (i = 1; i < num; i++) {<br />
for (j = 0; j < num - 1; j++) {<br />
if (iarr[j] > iarr[j + 1]) {<br />
temp = iarr[j];<br />
iarr[j] = iarr[j + 1];<br />
iarr[j + 1] = temp;<br />
}<br />
}<br />
printf("\nПосле %d итерације : ", i);<br />
for (k = 0; k < num; k++) {<br />
printf("%5d", iarr[k]);<br />
}<br />
}<br />
}<br />
<br />
 
Резултат програма <br />
 
void bubble_sort(int iarr[], int num) {
Унесите број елемената низа :5<br />
 
Унесите елементе :10 4 55 21 6<br />
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<br />
 
После 1 итерације : 4 10 21 6 55<br />
После 21 итерације : 4 10 21 6 21 55<br />
 
После 3 итерације : 4 6 10 21 55<br />
После 42 итерације : 4 10 6 10 21 55<br />
 
После 3 итерације : 4 6 10 21 55
 
После 4 итерације : 4 6 10 21 55
 
== Слични алгоритми ==
Слични овом алгоритму је алгоритам [[Koktel sortiranje|коктел сортирање]] он ради на истом принципу као и баблсорт само сто у једној итерацији пролази кроз низ прво са леве па онда са десне стране.
Преузето из „https://sr.wikipedia.org/wiki/Sortiranje_mehurom”