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

Сортирането по балон не само не се счита за най-бързия метод, освен това затваря списъка с най-бавните начини за поръчване. Има обаче и предимства. Така че сортирането по метода на балона е най-логичното и естествено решение на проблема, ако искате да подреждате елементите в определен ред. Един обикновен човек, например, ще го използва ръчно, просто чрез интуиция.

Откъде дойде това необичайно име?

Името на метода е измислено като се използва аналогия с въздушните мехурчета във вода. Това е метафора. Точно както малки въздушни мехурчета се издигат нагоре - поради тяхната плътност е по-голяма от течност (в този случай - вода), и всеки елемент масив, по-малка е стойността, толкова по постепенен начин в началото на номерата на списък.

Описание на алгоритъма

Сортирането по балон се извършва, както следва:

• първият пропуск: елементите на масива от числа се вземат в две и също се сравняват по двойки. Ако в някои два елемента първата стойност е по-голяма от втората, програмата прави размяната на места;
• Ето защо, най-големият брой пада в края на масива. Докато останалите елементи остават в хаотичен ред и се нуждаят от по-нататъшно сортиране;
• следователно е необходим и втори път: той се получава по аналогия с предишния (вече описан) и има редица сравнения - минус едно;
• в прохода, числото три сравнения е по-малко от второто и две от първото. И така нататък;
• Нека обобщим, че всеки пропуск има (в масива, конкретно число) минус (брой преходи) сравнения.

Дори по-кратък алгоритъм на бъдещата програма може да бъде написан както следва:

• масивът от числа се проверява, докато не се намерят две числа, втората от които трябва да е по-голяма от първата;
• неправилно разположени по отношение на всеки друг елемент на масива, програмата се заменя.

Псевдокод, базиран на описания алгоритъм

Най-простото изпълнение е следното:

процедура Sortirovka_Puzirkom-

Началото

цикъл за к от nachalnii_index до konechii_index-

цикъл за аз от nachalnii_index до konechii_index-1-

ако масив [i]> масив [i + 1] (първият елемент е по-голям от втория), след това:

(промяна на стойностите на места) -

Краят

Разбира се, тук простотата изостря ситуацията: колкото по-прост е алгоритъмът, толкова повече показва всички недостатъци. Консумацията на време е прекалено голяма дори за малък масив (тук идва относителността: за средния човек времето може да изглежда малко, но във всеки секунда на програмиста или дори милисекунда по сметката).

Необходимо е по-добро изпълнение. Например, като се има предвид обменът на стойности в масива на някои места:

процедура Sortirovka_Puzirkom-

Началото

sortirovka = true-

цикъл до sortirovka = true-

sortirovka = лъжа-

цикъл за аз от nachalnii_index до konechii_index-1-

ако масив [i]> масив [i + 1] (първият елемент е по-голям от втория), след това:

(смените елементи на места) -

sortirovka = true (посочва, че е извършена размяната).

Краят.

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

Основният недостатък е продължителността на процеса. Колко време отнема? алгоритъм за сортиране един балон?

Времето за изпълнение се изчислява от квадрата на броя на числата в масива - крайният резултат е пропорционален на него.

При най-лошия сценарий масивът ще бъде преместван толкова пъти, колкото има елементи в него, минус една стойност. Това е така, защото в крайна сметка има само един елемент, който няма какво да сравнява и последният пропуск през масива става безполезно действие.

В допълнение, методът на сортиране чрез обикновени обмени, както се нарича, е ефективен само за масиви с малки размери. Големи количества данни не могат да се обработват с него: резултатът ще бъде или грешка, или неизправност на програмата.

достойнство

Сортирането на балонче е много лесно разбираемо. В учебните планове на техническите университети, когато изучаваме поръчването на елементите на масива, преминава първо. Методът се изпълнява лесно както в програмния език на Delphi (D (Delphi), така и в C / C ++ (C / C плюс), невероятно прост алгоритъм за организиране на стойностите в правилния ред и на Паскал (Паскал). Сортирането на балони е идеално за начинаещи.

Поради недостатъци алгоритъмът не се използва за извънкласни цели.

Ясен принцип на сортиране

Първият изглед на масива е 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: масив [1..kol_mas] на integer-

a, b, k: цяло число-

започвам

writeln ("вход", kol_mas, "елементи на масив") -

за: = 1 до kol_mas do readln (масив [а]) -

за: = 1 до kol_mas-1 да започне

за b: = a + 1 до kol_mas да започне

ако massiv [a]> massiv [b] след това започне

k = масив [a] - масив [a]: = масив [b] - масив [b]: = k-

крайния

крайния

крайния

writeln ("след сортиране") -

за: = 1 до kol_mas do writeln (massiv [a]) -

край.

Пример за сортиране с балон в С (С)

например:

#include

#include

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

{

int масив [8] = {36, 697, 73, 82, 68, 12, 183, 88}, i, ff-

за (- -) {

ff = 0-

за (i = 7-i> 0-i -) {

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

суап (масив [i], масив [i-1]) -

ff ++ -

}

}

ако (ff == 0)

}

getch () - // забавяне на екрана

връщане 0-

}.