Сортування методом обміну
Delphi site: daily Delphi-news, documentation, articles, review, interview, computer humor.
В основі алгоритму лежить обмін сусідніх елементів масиву. Кожен елемент масиву, починаючи з першого, порівнюється з наступним, і якщо він більший за наступний, то елементи змінюються місцями. Таким чином, елементи з меншим значенням просуваються до початку масиву (спливають), а елементи з більшим значенням - до кінця масиву (тонуть). Тому даний метод сортування обміном іноді називають методом "бульбашка". Цей процес повторюється стільки разів, скільки елементів у масиві мінус одиниця.
На рис. 5.16 цифрою 1 позначено вихідний стан масиву та перестановки на першому проході, цифрою 2 - стан після перестановок на першому проході та перестановки на другому проході тощо.
Мал. 5.16. Процес сортування масиву
Мал. 5.17. Діалогове вікно програми Сортування методом обміну
На рис. 5.17 наведено діалогове вікно програми сортування масиву шляхом обміну.
Процедура сортування, текст якої наведено у лістингу 5.10, запускається натисканням кнопки Сортування (ви1:1:оп1). Значення елементів масиву вводяться з осередків компонента 31г:тдСг1а1. Під час сортування після виконання чергового циклу обмінів елементів масиву програма виводить масив у поле мітки ЬаЬе12.
I Лістинг 5.10. Сортування масиву шляхом обміну
до:integer; // поточний елемент масиву
i:integer; // Індес для введення та виведення масиву
changed:boolean; // TRUE, якщо у поточному циклі були обміни
buf:integer; // Буфер обміну елементами масиву
// сортування масиву repeat
changed:=FALSE; // нехай у поточному циклі немає обмінів
until not changed; // якщо був обмінів, значить // масиввідсортовано
Слід зазначити, що максимальна кількість циклів перевірки сусідніх елементів масиву дорівнює кількості елементів масиву мінус один. Разом з тим, можливо, що масив реально буде впорядкований за меншу кількість циклів. Наприклад, послідовність чисел 5 1 2 3 4, якщо її розглядати як подання масиву, буде впорядкована за один цикл, і виконання трьох циклів, що залишилися, не матиме сенсу.
Тому в програму введена логічна змінна changed, якій перед виконанням чергового циклу надається значення false. Процес сортування (цикл repeat) завершується, якщо після виконання чергового циклу перевірки сусідніх елементів масиву (цикл for), жоден елемент масиву не був обмінений із сусіднім, і, отже, масив вже впорядкований.
Мал. 5.18. Приклад роботи програми сортування масиву методом обміну
На рис. 5.18 наведено діалогове вікно програми сортування масиву методом обміну після завершення процесу сортування.