Методе сортирања у програмирању: сортирање по "буббле"

Сортирање балоном се не сматра само најбржим методом, већ се затвара листа најспоријих начина наручивања. Међутим, има и своје предности. Дакле, сортирање методом мехурица је најлогичније и природно решење проблема, ако желите да уредите елементе у одређеном редоследу. Обична особа ће, на пример, користити ручно, једноставно интуицијом.

Одакле је дошло ово необично име?

Име методе је измишљено користећи аналогију са ваздушним мехурићима у води. Ово је метафора. Баш као што се мали мехурићи зрака повећавају на врху - јер је њихова густина већа од било које течности (у овом случају - воде), а сваки елемент у низу, мањи је у вредности, то више постепено прелази на почетак листе бројева.

Опис алгоритма

Сортирање балона се врши на следећи начин:

• Први пас: елементи низа бројева се узимају у два и упоређују се у паровима. Ако је у неким двоје елемената прва вриједност већа од друге, програм врши размјену мјеста;
• Због тога је највећи број на крају низа. Иако сви остали елементи остају, какви су били, у хаотичном реду и захтевају даље сортирање;
• Дакле, потребан је други пасус: произведен је аналогно претходном (већ описан) и има неколико поређења - минус један;
• На пролазу, број три успоредбе је један мање од другог, а деуце је два од првих. И тако даље;
• Сумирамо да свака пасус има (у низу, одређени број) минус (број прелаза) поређења.

Још краћи алгоритам будућег програма може се написати на следећи начин:

• Низ бројева се проверава док се не пронађу два броја, од којих други мора бити већи од првог;
• Неправилно се лоцирају у односу на друге елементе низа, програм се замењује.

Псеудоцоде базиран на описаном алгоритму

Најједноставнија имплементација је следећа:

Процедура Сортировка_Пузирком ;

Почни

Петља за ј од нацхалнии_индек до конецхии_индек ;

Петља за и од нацхалнии_индек до конецхии_индек-1 ;

Ако масив [и]> масив [и + 1] (први елемент је већи од другог), онда:

(Промените вредности на местима);

Крај

Наравно, овде једноставност само погоршава ситуацију: што је једноставнији алгоритам, то више показује све недостатке. Дуготрајно је превише сјајно чак и за мали низ (овде долази релативност: за просечну особу, колико времена може изгледати мало, али у програмерској сваке секунде или чак милисекунди на рачуну).

Требало је боље имплементације. На пример, узимајући у обзир размјену вриједности у низу на неким мјестима:

Процедура Сортировка_Пузирком ;

Почни

Сортировка = труе;

Циклус док сортировка = труе;

Сортировка = фалсе;

Петља за и од нацхалнии_индек до конецхии_индек-1 ;

Ако масив [и]> масив [и + 1] (први елемент је већи од другог), онда:

(Променимо елементе на местима);

Сортировка = труе; (Означено да је извршена размена).

Крај.

Недостаци методе

Главни недостатак је трајање процеса. Колико дуго функционише алгоритам сортирања балона?

Време извршења се израчунава из квадрата броја бројева у низу - коначни резултат је сразмеран.

Са најгорим сценаријем, низ ће бити пролазан толико пута колико има елемената у њему, минус једна вредност. То је зато што на крају постоји само један елемент који нема ништа са којим треба упоредити, а последњи пролаз кроз низ постаје бескорисна акција.

Поред тога, метод сортирања једноставним размјенама, како се назива, дјелотворан је само за низове малих димензија. Велике количине података не могу се обрадити помоћу њега: резултат ће бити или грешке или пад програма.

Предности

Сортирање балона је веома лако разумјети. У наставним плановима и програмима техничких универзитета, када проучава наручивање елемената низова, прво прође. Метод се лако имплементира и на Делпхи програмском језику (Д (Делпхи) и Ц / Ц ++ (Ц / Ц плус плус)), невероватно једноставан алгоритам за уређивање вредности у исправном редоследу и за Пасцал (Пасцал) . Сортирање са балоном је идеално за почетнике.

Због недостатака, алгоритам се не користи за ваннаставне сврхе.

Јасан принцип сортирања

Иницијални приказ поља је 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 2 3 4 5 6 7 8

1 2 3 4 5 6 7 8

1 2 3 4 5 6 7 8 9

1 2 3 4 5 6 7 8 9

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

1 2 3 4 5 6 7 8 9

1 2 3 4 5 6 7 8 9

1 2 3 4 5 6 7 8 9

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

1 2 3 4 5 6 7 8 9

1 2 3 4 5 6 7 8 9

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

1 2 3 4 5 6 7 8 9 10

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

Пример сортирања балоном у Пасцалу

Пример:

Конст кол_мас = 10;

Вар масив: низ [1..кол_мас] целог броја;

А, б, к: интегер;

Почните

Врителн ('инпут', кол_мас, 'елементи низова');

За а: = 1 до кол_мас до реадлн (масив [а]);

За а: = 1 до кол_мас-1 почиње

За б: = а + 1 до кол_мас почињу

Ако масив [а]> масив [б] онда започне

К: = масив [а]; Массив [а]: = масив [б]; Массив [б]: = к;

Крај;

Крај;

Крај;

Врителн ('после сортирања');

За а: = 1 до кол_мас до врителн (масив [а]);

Крај.

Пример сортирања помоћу балона у Ц (Ц)

Пример:

#инцлуде

#инцлуде

Инт маин (инт аргц, цхар * аргв [])

{

Инт массив [8] = {36, 697, 73, 82, 68, 12, 183, 88}, и, фф;

За (;;) {

Фф = 0;

За (и = 7; и> 0; и -) {

Ако (масив [и] <масив [и-1]) {

Свап (масив [и], масив [и-1]);

Фф ++;

}

}

Ако (фф == 0) прекинете;

}

Гетцх (); // закашњење екрана

Повратак 0;

}.