Сортування обміном (також відоме як сортування методом бульбашки) полягає в тому, що всі сусідні єлементі вихідного масиву попарно порівнюються один з одним і міняються місцями, якщо попередній єлемент більший, або менший в залежності від типу сортування (за зростанням чи за спаданням) від наступного. В результаті максимальний (мінімальний) елемент поступово зміщується вправо і після першого такого перегляду займе крайнє праве положення. Потім процес перегляду повторюється, і своє місце займає другий за величиною елемент, який також виключається з подальшого розгляду. Продовжуючи даний процес далі, на останньому кроці отримаємо впорядковану послідовність.
Після того, як основна ідея алгоритму відома, реалізуємо, з його допомогою, процедуру сортування одновимірного масиму за зростанням, в середовищі програмування delphi. Для цього, запустимо delphi, та у вікні що появиться розмістимо наступні компоненти:
Далі, перейдемо до обробника події OnClick компонента Button1 («Сортувати»), і в тілі процедури Button1Click запишемо код, з допомогою якого будемо заповнювати одновимірний масива X та таблицю StringGrid1 випадковими значеннями. Після цього, реалізуємо процес сортування масиву X методом бульбашки, та здійснимо його вивід у в компоненті StringGrid2.
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, що свідчитиме про те, що необхідно здійснити перегляд масиву ще раз.
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.
Дуже гарна і робоча реалізація. Дякую.