Сортування одновимірного масиву методом бульбашки (сортування обміном)

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

Сортування обміном

Сортування обміном

Після того, як основна ідея алгоритму відома, реалізуємо, з його допомогою, процедуру сортування одновимірного масиму за зростанням, в середовищі програмування delphi. Для цього, запустимо delphi, та у вікні що появиться розмістимо наступні компоненти:

Головна форма delphi-проекту "Сортування обміном"

Головна форма delphi-проекту "Сортування обміном"

Далі, перейдемо до обробника події OnClick компонента Button1 («Сортувати»), і в тілі процедури Button1Click запишемо код, з допомогою якого будемо заповнювати одновимірний масива X та таблицю StringGrid1 випадковими значеннями. Після цього, реалізуємо процес сортування масиву X методом бульбашки, та здійснимо його вивід у в компоненті StringGrid2.

procedure TForm1.Button1Click(Sender: TObject);
var
X, Y: array[0..6] of integer;
i, j, min_i, c: integer;
begin
// Заповнюємо масиви X та таблицю StringGrid1 випадковими даними
randomize;
for i := 0 to StringGrid1.ColCount — 1 do
begin
X[i] := Random(100);
StringGrid1.Cells[i, 0] := IntToStr(X[i]);
end;
// Сортуємо масив X
for i := 0 to StringGrid1.ColCount — 1 do
for j := 0 to StringGrid1.ColCount — 2 — i do
if (X[j] > X[j + 1]) then
begin
c := X[j];
X[j] := X[j + 1];
X[j + 1] := c;
end;
// Виводимо відсортований масив X у компоненті StringGrid2
for i := 0 to StringGrid1.ColCount — 1 do
StringGrid2.Cells[i, 0] := FloatToStr(X[i]);
end;

Далі, зберігши, відкомпілювавши та запустивши проект на виконання, скориставємось кнопкою «Сортувати». В результаті отримаємо:

Результат роботи програми "Сортування обміном"

Сортування обміном без фіксування факту обміну

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

Для усунення даного недоліку зазвичай використовують більш ефективний варіант методу бульбашки, який полягає у фіксуванні факту обміну. Тобто, якщо факт обміну при черговому перегляді масиву не фіксується, то процес сортування завершується. В іншому випадку, сортування продовжується.

Далі, доповнимо створений на попередньому кроці delphi-проект, ще одною кнопкою типу TButton і на обробник події OnClick даної кнопки реалізуємо процедуру сортування масиву з фіксуванням факту обміну. Відмітимо, що програмний код даної процедури буде аналогічним процедурі Button1Click лише з однією відмінністю. В тілі процедури Button2Click, створимо додаткову змінну substitute, яка перед початком чергового перегляду прийматиме значення 0. Якщо в процесі перегляду відбувається обмін значень, то змінна substitute прийме значення рівне 1, що свідчитиме про те, що необхідно здійснити перегляд масиву ще раз.

procedure TForm1.Button2Click(Sender: TObject);
var
X, Y: array[0..6] of integer;
i, j, min_i, c, substitute: integer;
begin
// Заповнюємо масиви X та таблицю StringGrid1 випадковими даними
randomize;
for i := 0 to StringGrid1.ColCount — 1 do
begin
X[i] := Random(100);
StringGrid1.Cells[i, 0] := IntToStr(X[i]);
end;
// Сортуємо масив X
for i := 0 to StringGrid1.ColCount — 1 do
begin
substitute := 0;
for j := 0 to StringGrid1.ColCount — 2 — i do
if (X[j] > X[j + 1]) then
begin
c := X[j];
X[j] := X[j + 1];
X[j + 1] := c;
substitute := 1;
end;
if (substitute = 0) then
break;
end;
// Виводимо відсортований масив X у компоненті StringGrid2
for i := 0 to StringGrid1.ColCount — 1 do
StringGrid2.Cells[i, 0] := FloatToStr(X[i]);
end;

Далі, знову-таки збережемо, відкомпілюємо та запустимо delphi-проект на виконання. Після того, у вікні, що відкриється, скористаємось кнопкою «Сортувати з фіксуванням факту обміну». Результати роботи програми містяться на наступній формі:

Сортування обміном на delphi

Сортування обміном з фіксуванням факту обміну

Скачати створений в даному парагряфі delphi-проект можна перейшовши за посиланням Сортування обміном на delphi.

Блок-схема алгоритму cортування обміном без фіксування факту обміну

Сортування обміном блок-схема

Блок-схема алгоритму cортування обміном з фіксування факту обміну

Сортування обміном блок-схема

Матеріал був корисним, поділись в соціальних мережах:

Якщо тобі сподобалась дана тема, залиш свій коментар