Embedded Files
!!! У шеренгу стали 5 учнів. Порівняйте зріст перших двох. Якщо перший вищий за другого, поміняйте їх місцями, за потреби — другого і третього і т. д. Як розмістяться учні?
Сортування обміном (або бульбашкове сортування) - це найпростіший спосіб упорядкувати масив чисел, з точки зору витрат програмних ресурсів.
Ідея – бульбашка повітря в стакані води піднімається з дна вгору. Тобто найменший ("легкий") елемент переміщується вгору ("спливає"). А точніше, найбільший елемент опускається донизу.
Алгоритм
Порівнюємо два сусідніх елементи.
Якщо вони стоять не в порядку зростання, то переставляємо їх.
Повторюємо, поки всі елементи не стануть на свої місця.
Для сортування масиву з N елементів потрібен N-1 прохід , тобто достатньо поставити на свої місця N -1 елемент.
Розглянемо сутність алгоритму сортування масиву в порядку зростання значень його елементів методом обміну.
З описаного випливає, що ознакою упорядкованості масиву є те, що після завершення його перегляду жодної перестановки елементів не було. У прикладі 2 наведено порядок переміщення максимального числа на крайню праву позицію у масиві [4, 2, 5, 7, 6, 1]. Жирним шрифтом виділено елементи, які порівнюються.
Отже, після першого перегляду масиву елемент із максимальним значенням буде розташований на останній позиції. Розробимо алгоритм сортування методом обміну. В алгоритмі використано такі позначення: p — індекс правої межі поточної ділянки масиву; y — ознака наявності перестановки: на початку кожного зовнішнього циклу y набуває значення True. Якщо після завершення зовнішнього циклу вона має значення True, це означає, що перестановок під час останнього перегляду не було; якщо y = False, то відбулася принаймні одна перестановка; i — індекс поточного елемента масиву; z — змінна, призначена для тимчасового зберігання значення елемента масиву під час перестановки елементів. Розглянемо алгоритм сортування масиву методом обміну, який може бути таким.
Програму реалізації алгоритму сортування методом обміну зображено на рисунку:
У результаті виконання програми отримаємо: 7, 16, 20, 31, 51, 63, 100.
Практичне завдання ( для самостійного виконання).
Практичне завдання ( для самостійного виконання).
Увага! Під час роботи з комп'ютером дотримуйтеся вимог безпеки життєдіяльності та санітарно-гігієнічних норм.
Завдання 1. Визначте кількість операцій порівняння в алгоритмі сортування методом обміну в процесі впорядкування масиву 100, 20, 41,30, 35.
Завдання 2. Дано масив чисел: 34, 12, 8, 5, 20, 17. Виконайте його сортування за допомогою методу обміну в порядку зменшення чисел.
Завдання 3. Створити проєкт, зображений на малюнку.
Page updated
Google Sites
Report abuse