В основі алгоритму лежить обмін сусідніх елементів масиву. Кожен елемент масиву, починаючи з першого, порівнюється з наступним, і якщо він повинна перевищувати, то елементи міняються місцями. Таким чином, елементи з меншим значенням просуваються до початку масиву (Спливають), а елементи з великим значенням – до кінця масиву (тонуть). Тому даний метод сортування обміном іноді називають методом “бульбашки”. Цей процес повторюється стільки раз, скільки елементів в масиві, мінус одиниця.
На рис. 5.17 цифрою 1 позначено вихідне стан масиву і перестановки на першому проході, цифрою 2 – стан після перестановок на першому проході і перестановки на другому проході, і т. д.
Рис. 5.17. Процес сортування масиву
Рис. 5.18. Діалогове вікно програми Сортування методом обміну
На рис. 5.18 приведено діалогове вікно програми сортування масиву методом обміну.
Процедура сортування, текст якої наведено в лістингу 5.10, запускається натисканням кнопки Сортування (Button1). Значення елементів масиву вводяться з осередків компонента stringGrid1. Під час сортування, після виконання чергового циклу обмінів елементів масиву, програма виводить масив в поле мітки Label2.
Лістинг 5.10. Сортування масиву методом обміну
procedure TForm1.Button1Click (Sender: TObject); const SIZE = 5; var a: array [1..SIZE] of integer; k: integer; // поточний елемент масиву i: integer; // індекс для введення і виведення масиву changed: boolean; // TRUE, якщо в поточному циклі були обміни buf: integer; // буфер для обміну елементами масиву begin // введення масиву for i: = 1 to SIZE do a [i] : = StrToInt (StringGrid1.Cells [i-1, 0]); label2.caption: = ''; // сортування масиву repeat Changed: = FALSE; // нехай в поточному циклі немає обмінів for k: = l to SIZE-1 do if a [k] > a [k + l] then begin // обміняємо k-й і k + 1-й елементи buf : = A [k]; a [k]: = a [k + l]; a [k + l]: = buf; changed : = TRUE; end; // висновок масиву for i: = l to SIZE do Label2.caption: = label2.caption + ' '+ IntTostr (a [i]); Label2.caption: = label2.caption + # 13; until not changed; // якщо не було обмінів, значить // масив відсортований Label2.caption: = label2.caption + # 13 + 'Maccів відсортований. '; end;
Слід зазначити, що максимальне необхідну кількість циклів перевірки сусідніх елементів масиву дорівнює кількості елементів масиву мінус один. Разом з тим можливо, що масив реально буде впорядкований за менше число циклів. Наприклад, послідовність чисел 5 1 2 3 4, якщо її розглядати як уявлення масиву, буде впорядкована за один цикл, і виконання інших трьох циклів не матиме сенсу.
Тому в програму введена логічна змінна changed, якій перед виконанням чергового циклу присвоюється значення FALSE. Процес сортування (цикл repeat) завершується, якщо після виконання чергового циклу перевірки сусідніх елементів масиву (цикл for) жоден елемент масиву не був обміняний з сусіднім, і, отже, масив вже впорядкований.
Рис. 5.19. Приклад роботи програми сортування масиву методом обміну
На рис. 5.19 приведено діалогове вікно програми сортування масиву методом обміну після завершення процесу сортування.