Сортування методом «Бульбашка»

Цей метод дуже простий, але працює досить повільно. Метод є розвитком обмінного сортування, заснований на попарному порівнянні суміжних елементів даних; якщо порядок проходження елементів у черговій парі неправильний, то ці елементи міняються місцями. Для виконання обміну потрібна проміжна комірка. Процес закінчується, коли масив відсортовано, про що свідчить відсутність обмінів при черговому проході по масиву (р=0).

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

Таблиця 2

АЛГ Метод бульбашки (ціл k, n, дійсн таб A[k:n])

АРГ k, n, A

РЕЗ А

ПОЧ ціл і, р, дійсн R

p:=1

поки р

пц

р:=0

для і від 1 до n – 1

пц

якщо A[i]>A[i+1]

то R:=A[i]

A[i]:=A[i+1]

A[i]:=R

p:=p+1

Все

кц

кц

КІН

Тут використовується комірка р, ознака. Вона набуває значення 0, якщо перестановок елементів у масиві не було, це означає, що масив упорядкований, і не дорівнює 0, якщо перестановки – були. На початку передбачається, що масив не впорядкований, тобто р=1. Організовується цикл з умовою , тобто масив не впорядкований.

Увійшовши в цикл, передбачається, що масив уже відсортований (р=0), хоча, звичайно ж, це не так. Далі організовується внутрішній цикл, у якому виконується попарно порівняння елементів. І якщо елементи масиву не впорядковані, то відбудеться перестановка елементів місцями. Уміст р стане рівним 0 і зовнішній цикл знову почне роботу. Вихід із зовнішнього циклу відбудеться тоді, коли перестановок елементів не буде (р=0), а це значить, що масив упорядкований.

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

У цьому методі останній прохід наче зайвий. Він виконується вже по впорядкованій таблиці, але це необхідно, щоб переконатися в тому, що перестановок елементів уже не буде.

У програмуванні мовою Паскаль зручно використовувати змінну логічного (boolean) типу – прапорець, яка набуватиме значення true, якщо зроблена хоч одна перестановка. Значення false їй надається перед початком проходу по масиву, що ототожнюється з припущенням відсортованості масиву.

const n=300;

type arr = array [1..n] of real;

Procedure Bubble (var M: arr);

var i: word; e1: real; flag: boolean;

Begin

flag:=true;

while flag do

Begin

flag:=false;

for i:=1 to n – 1 do

if M[i]>M[i+1]

Поиск по сайту: