Методи сортування в програмуванні: сортування "бульбашкою"

Сортування бульбашкою не тільки не вважається самимшвидким методом, більш того, вона замикає перелік самих повільних способів упорядкування. Однак і у неї є свої плюси. Так, сортування методом бульбашки - саме що ні на є логічне і природне рішення проблеми, якщо необхідно розставити елементи в певному порядку. Звичайна людина вручну, наприклад, скористається саме їм - просто по інтуїції.

Звідки взялося таке незвичайне назва?

Назва методу придумали, використовуючи аналогію зповітряними бульбашками в воді. Це метафора. Подібно до того, як маленькі бульбашки повітря піднімаються нагору - адже їх щільність більше, ніж будь-якої рідини (в даному випадку - води), так і кожен елемент масиву, чим менше він за значенням, тим більше він поступово пробирається до початку переліку чисел.

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

Сортування бульбашкою виконується наступним чином:

• перший прохід: елементи масиву чисел беруться за два і також парами порівнюються. Якщо в якийсь двійці елементів перше значення виявляється більше другого, програма робить їх обмін місцями;
• отже, найбільше число потрапляє в кінець масиву. У той час як всі інші елементи залишаються, як і були, в хаотичному порядку і вимагають ще сортування;
• тому й потрібен другий прохід: проводиться він за аналогією з попереднім (вже описаним) і має число порівнянь - мінус один;
• біля проходу номер три порівнянь на одиницю менше, ніж у другого, і на двійку, ніж у першого. І так далі;
• підсумуємо, що кожен прохід має (всього значень в масиві, конкретне число) мінус (номер проходу) порівнянь.

Ще коротше алгоритм майбутньої програми можна записати так:

• масив чисел перевіряється до тих пір, поки не будуть знайдені якісь два числа, причому другий з них має перевищувати першого;
• неправильно розташовані по відношенню один до одного елементи масиву програма міняє місцями.

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

Найпростіша реалізація виконується так:

процедура Sortirovka_Puzirkom;

початок

цикл для ж від nachalnii_index до konechii_index;

цикл для і від nachalnii_index до konechii_index-1;

якщо massiv [i]> massiv [i + 1] (Перший елемент більше другого), то:

(Міняємо значення місцями);

кінець

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

Потрібна була реалізація краще. Наприклад, враховує обмін значень в масиві місцями:

процедура Sortirovka_Puzirkom;

початок

sortirovka = Істина;

цикл поки sortirovka = Істина;

sortirovka = Брехня;

цикл для і від 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] <massiv [i-1]) {

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

ff ++;

}

}

if (ff == 0) break;

}

getch (); // затримка екрану

return 0;

}.