Техники в програмирането сортиране: сортиране "балон"

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

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

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

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

метод на мехурчето се извършва, както следва:

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

Дори и по-кратък алгоритъм на програма може да се запише като:

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

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

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

процедура Sortirovka_Puzirkom;

начало

цикъл й от nachalnii_index да konechii_index;

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

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

(Промяна поставя ценности);

край

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

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

процедура Sortirovka_Puzirkom;

начало

sortirovka = вярно;

цикъл до sortirovka = вярно;

sortirovka = фалшива;

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

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

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

sortirovka = вярно; (Установено, че размяната е направена).

Край.

Ограничения

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

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

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

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

достойнство

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

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

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

Първоначалната изглед на масива 8 22 4 74 44 37 1 7

Етап 8 22 4 1 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

Стъпка 1 8 22 2 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

Стъпка 1 4 8 3 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

Стъпка 1 4 7 4 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

Стъпка 1 4 7 5 8 22 37 44 74

1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Стъпка 1 4 7 6 8 22 37 44 74

1 4 7 8 22 37 44 74

Стъпка 1 4 7 7 8 22 37 44 74

метод на мехурчето например в Паскал

например:

CONST kol_mas = 10;

Var Massiv: масив [1..kol_mas] на цяло число;

а, Ь, к: цяло число;

започвам

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

за: = 1 до kol_mas направи readln (Massiv [а ]);

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

за б: = а + 1 до kol_mas се започне

ако Massiv [а]> Massiv [ Ь] след това започва

к: = Massiv [а]; Massiv [а]: = Massiv [ Ь]; Massiv [Ь]: = к;

приключи;

приключи;

приключи;

writeln ( 'след сортиране');

за: = 1 до kol_mas направи writeln (Massiv [а ]);

край.

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

например:

#include

#include

Int основна (междинно argc, знак * argv [])

{

Int Massiv [8] = {36, 697, 73, 82, 68, 12, 183, 88}, I, ее;

за (;;) {

ее = 0;

за (I = 7; I> 0; I -) {

ако (Massiv [Ь] [i- 1]) {

размяна (Massiv [Ь] Massiv [i- 1]);

ее ++;

}

}

ако (ее == 0) прекъсване;

}

getch (); // забавяне дисплей

връщане 0;

}.