Нехай маємо послідовність, наприклад, для простоти викладення, з 5 чисел
2 5 1 0 6
записану у масив “a”, тобто a[1]=2, a[2]=5, a[3]=1, a[4]=0 i a[5]=6.
Нашою задачею є переставити ці числа за зростанням, тобто таким чином, щоб на першому місці було найменше число, за ним більше і т.д. останнім має стояти найбільше число.
Алгоритм бульбашкового сортування діє таким чином: послідовно порівнюються сусідні елементи послідовності (масиву) і, якщо те, що розташоване лівіше, є більшим за те, що розташоване правіше – їх значення переставляють місцями. Так треба перевірити всі послідовні сусідні пари у масиві. У нашому випадку це матиме вигляд:
| Стан масиву до перевірки
| Елементи, які порівнюються
| Результат порівняння
| Стан масиву після перевірки та перестановки
|
| 2 5 1 0 6
| a[1] > a[2]
| ні
| 2 5 1 0 6
|
| 2 5 1 0 6
| a[2] > a[3]
| так
| 2 1 5 0 6
|
| 2 1 5 0 6
| a[3] > a[4]
| так
| 2 1 0 5 6
|
| 2 1 0 5 6
| a[4] > a[5]
| ні
| 2 1 0 5 6
|
Таким чином на першому етапі застосування бульбашкового методу сортування ми “виставили” найбільший елемент масиву на своє місце (тобто у хвіст масиву). Наступним кроком є перевірка вже не всіх чотирьох сусідніх послідовніх пар елементів, а лише перших трьох (останній елемент вже є найбільшим і перевіряти його нема потреби). Отже:
| Стан масиву до перевірки
| Елементи, які порівнюються
| Результат порівняння
| Стан масиву після перевірки та перестановки
|
| 2 1 0 5 6
| a[1] > a[2]
| так
| 1 2 0 5 6
|
| 1 2 0 5 6
| a[2] > a[3]
| так
| 1 0 2 5 6
|
| 1 0 2 5 6
| a[3] > a[4]
| ні
| 1 0 2 5 6
|
Тобто на другому етапі ми визначили передостанній елемент масиву.
Відповідно на наступному кроці отримаємо
0 1 2 5 6
і на останньому
0 1 2 5 6
тепер формально запишемо перший етап, вважаючи, що у нас є ще ціла змінна і:
| for i:=1 to 4 do
if a[i]>a[i+1] then
begin
a[i]:=a[i]+a[i+1];
a[i+1]:=a[i]‑a[i+1];
a[i]:=a[i]‑a[i+1];
end;
|
Якщо значення поточної змінної, більше за значення наступної, то переставити значення місцями
Тут є перестановка значень двох змінних місцями. Див. “Перестановка двох значень змінних без використання додаткової змінної.“
|
Наступна ітерація матиме вигляд
for i:=1 to 3 do
if a[i]>a[i+1] then
begin
a[i]:=a[i]+a[i+1];
a[i+1]:=a[i]‑a[i+1];
a[i]:=a[i]‑a[i+1];
end;
Тобто всього ітерацій нам треба зробити чотири – для і=1..4, і=1..3, і=1..2 та і=1. Досягти цього можна ввівши ще одну цілу змінну, наприклад j і використати її для вкладеності циклу
for j:=1 to 4
for i:=1 to 5‑j do
if a[i]>a[i+1] then
begin
a[i]:=a[i]+a[i+1];
a[i+1]:=a[i]‑a[i+1];
a[i]:=a[i]‑a[i+1];
end;
Відмітимо, що у прикладі у нас масив складається з 5 елементів а цикл для проходу по масиву ми організовуємо від 1 до 4. Це робиться через те, що ми порівнюємо на кожній ітерації поточний елемент масиву з наступним. Якби ми організували цикл від 1 до 5, то на останньому кроці відбувалося б порівнянн 5-го елементу з 5+1-м, тобто 6-м, а такого немає.
Алгоритм бульбашкового сортування маству за спаданням має такий самий вигляд що і за зростанням, тільки знак > у операторі if слід поміняти на <.
Продовження прикладу використання циклу for to do.
У нашому випадку сам фрагмент програми з реалізацією алгоритму бульбашкового сортування, має вигляд
for j:=1 to 99 do
for i:=1 to 100-j do
if a[i]>a[i+1] then
begin
a[i]:=a[i]+a[i+1];
a[i+1]:=a[i]-a[i+1];
a[i]:=a[i]-a[i+1];
end;
і останнім кроком роботи програми є виведення відсортованого масиву у ListBox2. Цей фрагмент програми матиме вигляд
for i:=1 to 100 do
Listbox2.Items.Append(inttostr(a[i]));
Отже вся процедура (головна подія для Button2) має вигляд
procedure TForm1.Button2Click(Sender: TObject);
begin
for j:=1 to 99 do
for i:=1 to 100-j do
if a[i]>a[i+1] then
begin
a[i]:=a[i]+a[i+1];
a[i+1]:=a[i]-a[i+1];
a[i]:=a[i]-a[i+1];
end;
for i:=1 to 100 do
Listbox2.Items.Append(inttostr(a[i]));
end;
І нарешті, виходячи з того, що під час роботи програми ми можемо генерувати масив А довільну кількість разів і він буде виводитись у ListBox1 та сортований у ListBox2, то щоразу новозгенерований масив буде дописуватись у кінець ListBox1 та ListBox2 відповідно, тобто з часом у ListBox1 та ListBox2 почнеться плутанина. Щоб запобігти цьому досить просто очищати вміст ListBox1 та ListBox2 перед кожним записом масиву у них. Здійснити це легко за допомогою процедури ListBox1.Items.Clear та ListBox2.Items.Clear.
Весь текст програми матиме вигляд
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
StdCtrls;
type
TForm1 = class(TForm)
Button1: TButton;
ListBox1: TListBox;
Button2: TButton;
ListBox2: TListBox;
procedure Button1Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
Form1: TForm1;
implementation
{$R *.DFM}
var
a:array [1..100] of integer;
i,j:integer;
procedure TForm1.Button1Click(Sender: TObject);
begin
ListBox1.Items.Clear;
ListBox2.Items.Clear;
for i:=1 to 100 do
begin
a[i]:=random(17);
ListBox1.Items.Append(inttostr(a[i]));
end;
end;
procedure TForm1.Button2Click(Sender: TObject);
begin
ListBox2.Items.Clear;
for j:=1 to 99 do
for i:=1 to 100-j do
if a[i]>a[i+1] then
begin
a[i]:=a[i]+a[i+1];
a[i+1]:=a[i]-a[i+1];
a[i]:=a[i]-a[i+1];
end;
for i:=1 to 100 do
Listbox2.Items.Append(inttostr(a[i]));
end;
end.
Розглянемо тепер роботу програми. Після її запуску на екран буде виведено вікно форми вигляду
Далі, після натискання на Button1, отримаємо згенерований масив зі 100 чисел, що виведено у ListBox1 і записано у масив а.
Після натискання на клавішу Button2 здійсюється сортування масиву а та виведення його у ListBox2.
Відмітимо, що так як ми використовуємо для генерування масиву функцію random, при кожному новому запуску програми або натисканню на клавішу Button1 ми отримаємо новий масив з іншими значеннями.
