Метады сартавання ў праграмаванні: сартаванне "бурбалкай"

Сартаванне бурбалкай не толькі не лічыцца самым хуткім метадам, больш за тое, яна замыкае пералік самых павольных спосабаў парадкавання. Аднак і ў яе ёсць свае плюсы. Так, сартаванне метадам бурбалкі - самае што ні на ёсць лагічнае і натуральнае рашэнне праблемы, калі неабходна расставіць элементы ў вызначаным парадку. Звычайны чалавек ўручную, да прыкладу, скарыстаецца менавіта ім - проста па інтуіцыі.

Адкуль узялося такое незвычайнае назву?

Назва метаду прыдумалі, выкарыстоўваючы аналогію з паветранымі бурбалкамі ў вадзе. Гэта метафара. Падобна таму, як маленькія бурбалкі паветра падымаюцца наверх - бо іх шчыльнасць больш, чым які-небудзь вадкасці (у дадзеным выпадку - вады), так і кожны элемент масіва, чым менш ён па значэнні, тым больш ён паступова прабіраецца да пачатку пераліку лікаў.

апісанне алгарытму

Сартаванне бурбалкай выконваецца наступным чынам:

• першы праход: элементы масіва лікаў бяруцца па два і таксама парамі параўноўваюцца. Калі ў нейкі двойцы элементаў першае значэнне аказваецца больш другога, праграма вырабляе іх абмен месцамі;
• такім чынам, найбольшая колькасць трапляе ў канец масіва. У той час як усе астатнія элементы застаюцца, як і былі, у хаатычным парадку і патрабуюць яшчэ сартавання;
• таму і неабходны другі праход: вырабляецца ён па аналогіі з папярэднім (ужо апісаным) і мае лік параўнанняў - мінус адзін;
• ля праходу нумар тры параўнанняў на адзінку менш, чым у другога, і на двойку, чым у першага. І гэтак далей;
• падагульнім, што кожны праход мае (усяго значэнняў у масіве, канкрэтнае лік) мінус (нумар праходу) параўнанняў.

Яшчэ карацей алгарытм будучай праграмы можна запісаць так:

• масіў лікаў правяраецца да таго часу, пакуль не будуць знойдзеныя якія-небудзь два ліку, прычым другое з іх павінна быць больш першага;
• няправільна размешчаныя ў адносінах адзін да аднаго элементы масіва праграма мяняе месцамі.

Псевдокод на аснове апісанага алгарытму

Самая простая рэалізацыя выконваецца так:

Працэдура Sortirovka_Puzirkom;

пачатак

цыкл для j ад nachalnii_index да konechii_index;

цыкл для i ад nachalnii_index да konechii_index-1;

калі massiv [i]> massiv [i + 1] (першы элемент больш другога), то:

(мяняем значэння месцамі);

канец

Вядома, тут прастата толькі пагаршае сітуацыю: чым прасцей алгарытм, тым больш у ім выяўляюцца ўсе недахопы. Затратнасць часу занадта вялікая нават для невялікага масіва (тут уступае ў справу адноснасць: для абывацеля колькасць часу можа здавацца маленькім, але ў справе праграміста кожная секунда ці нават мілісэкундах на рахунку).

Спатрэбілася рэалізацыя лепей. Напрыклад, якая ўлічвае абмен значэнняў у масіве месцамі:

Працэдура Sortirovka_Puzirkom;

пачатак

sortirovka = ісціна;

цыкл пакуль sortirovka = ісціна;

sortirovka = хлусня;

цыкл для i ад nachalnii_index да konechii_index-1;

калі massiv [i]> massiv [i + 1] (першы элемент больш другога), то:

(мяняем элементы месцамі);

sortirovka = ісціна; (пазначылі, што абмен быў выраблены).

Канец.

недахопы метаду

Асноўны мінус - працягласць працэсу. Колькі ж часу выконваецца алгарытм сартавання бурбалкай?

Час выканання разлічваецца з квадрата колькасці лікаў у масіве - канчатковы вынік яму прапарцыйны.

Пры найгоршым варыянце масіў будзе пройдзены столькі ж разоў, колькі ў ім маецца элементаў мінус адно значэнне. Так адбываецца таму, што ў канчатковым выніку застаецца толькі адзін элемент, які не з чым параўноўваць, і апошні праход па масіве становіцца бескарысным дзействам.

Акрамя таго, эфектыўны метад сартавання простымі абменамі, як яго яшчэ называюць, толькі для масіваў невялікага памеру. Вялікія аб'ёмы дадзеных з яго дапамогай апрацаваць не атрымаецца: вынікам стануць небудзь памылкі, альбо збой працы праграмы.

годнасці

Сартаванне бурбалкай вельмі простая для разумення. У навучальных праграмах тэхнічных ВНУ пры вывучэнні парадкавання элементаў масіва яе праходзяць у першую чаргу. Метад лёгка рэалізуецца як на мове праграмавання Delphi (Д (Дэлфі), так і на C / C ++ (Сі / Сі плюс плюс), неверагодна просты алгарытм размяшчэння значэнняў ў дакладным парадку і на Pascal (Паскаль). Сартаванне бурбалкай ідэальна падыходзіць для пачаткоўцаў.

Па прычыне недахопаў алгарытм не прымяняюць у пазанавучальных мэтах.

Наглядны прынцып сартавання

Першапачатковы выгляд масіва 8 22 4 74 44 37 1 7

Крок 1 8 22 4 74 44 37 1 7

8 22 4 74 44 1 37 7

8 22 4 74 1 44 37 7

8 22 4 1 74 44 37 7

8 22 1 4 74 44 37 7

8 1 22 4 74 44 37 7

1 8 22 4 74 44 37 7

Крок 2 1 8 22 4 74 44 7 37

1 8 22 4 74 7 44 37

1 8 22 4 7 74 44 37

1 8 22 4 7 74 44 37

1 8 4 22 7 74 44 37

1 4 8 22 7 74 44 37

Крок 3 1 4 8 22 7 74 37 44

1 4 8 22 7 37 74 44

1 4 8 22 7 37 74 44

1 4 8 7 22 37 74 44

1 4 7 8 22 37 74 44

Крок 4 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Крок 5 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Крок 6 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Крок 7 1 4 7 8 22 37 44 74

Прыклад сартавання бурбалкай на мове Pascal

прыклад:

const kol_mas = 10;

var massiv: array [1..kol_mas] of integer;

a, b, k: integer;

begin

writeln ( 'input', kol_mas, 'elements of array');

for a: = 1 to kol_mas do readln (massiv [a]);

for a: = 1 to kol_mas-1 do begin

for b: = a + 1 to kol_mas do begin

if massiv [a]> massiv [b] then begin

k: = massiv [a]; massiv [a]: = massiv [b]; massiv [b]: = k;

end;

end;

end;

writeln ( 'after sort');

for a: = 1 to kol_mas do writeln (massiv [a]);

end.

Прыклад сартавання бурбалкай на мове З (Сі)

прыклад:

#include

#include

int main (int argc, char * argv [])

{

int massiv [8] = {36, 697, 73, 82, 68, 12, 183, 88}, i, ff;

for (;;) {

ff = 0;

for (i = 7; i> 0; i -) {

if (massiv [i]

swap (massiv [i], massiv [i-1]);

ff ++;

}

}

if (ff == 0) break;

}

getch (); // затрымка экрана

return 0;

}.