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

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

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

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

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

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

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

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

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

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

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

Процедура 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] lt; massiv [i-1]) {

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

ff ++ -

}

}

if (ff == 0) break-

}

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

return 0-

}.