38.1.

Сортування методом бульбашок

Одним із найдавніших відомих методів сортування є сортування «бульбашками». Принцип цього методу полягає у попарному порівнянні елементів та обміну їх місцями, доки менші елементи не перестануть «спливати» до початку списку, а більші елементи не будуть «тонути» в кінець списку. Метод бульбашок ґрунтується на порівнянні та перестановці сусідніх чисел.

На рис. 38.1 візуально показано, як відбувається порівняння та обмін елементів масиву на прикладі сортування за зростанням списку [7, 4, 3, 5, 1].

З наведеного прикладу видно, що для реалізації даного алгоритму доцільно буде використати вкладений цикл. В зовнішньому циклі будемо визначати номер ітерації з допомогою змінної j. У внутрішньому циклі будемо перевіряти умову, де індекс елемента позначимо змінною і.

Так, для наведеного прикладу оператор зовнішнього циклу буде мати вигляд:

Розглянемо діапазон значень для внутрішнього тіла циклу для кожної ітерації:

для j = 1, і належить інтервалу [0,4]; для j=2, і належить інтервалу [0,3]; для j=3, і належить інтервалу [0,2]; для j=4, і належить інтервалу [0,1].

Отже, оператор внутрішнього циклу буде мати вигляд:

Для порівняння елементів доцільно скористатися оператором розгалуження:

Таким чином буде здійснюватися порівняння поточного елемента масиву з наступним. У разі виконання умови елементи необхідно поміняти місцями, використовуючи команду:

Отже, для сортування списку a=[7, 4, 3, 5, 1] за зростанням методом «бульбашок» програмний код буде таким:

ПРАКТИЧНЕ ЗАВДАННЯ 1.

Уведіть наведений вище код та перевірте правильність його виконання. Спробуйте самостійно змінити програму, аби сортування здійснювалося за спаданням елементів.

Нижче наведено алгоритм сортування масиву, що містить п елементів.

Алгоритм сортування масиву для n елементів:

1. Порівняти і-й елемент списку з i+1-м.

2. Поміняти елементи місцями:

а) для сортування за зростанням, якщо і-й елемент більший;

б) для сортування за спаданням, якщо і-й елемент менший.

3. Повторити описані вище дії від початку списку до останнього невідсортованого елемента включно.

ВПРАВА 38.1

Завдання. Виконати завдання вправи 37.1, застосувавши при сортуванні метод бульбашок.

1. Завантажте файл-заготовку Вправа_38_1^ із матеріалів до даного параграфа.

2. Створіть обробник події натискання кнопки За глибиною для сортування елементів за спаданням.

а. Створіть команду обробника події натискання кнопки та додайте оператор циклу сортування масиву depth за спаданням методом бульбашок:

b. Оскільки згідно з умовою відповідні дані, що розміщені в інших списках, мають переміщуватися на ті ж місця, що й глибини озер під час сортування, у тілі цього ж циклу додайте команди обміну елементами списків name та area.

c. Додайте команди очищення елементів керування Lbox_name, Lbox_depth, Lbox_area.

d. Додайте оператор циклу виведення відсортованих списків до елементів керування Lbox_name, Lbox_depth, Lbox_area.

3. Додайте команду виклику обробника події в конструкторі кнопки За глибиною.

4. Обробники подій натискання кнопок За назвою та За площею створіть самостійно.

ВПРАВА 38.2

Завдання. Дано список переможців олімпіади з інформатики (рис. 38.2). Створити обробник події для кнопки Призові місця, що має:

виконувати сортування призерів олімпіади за рейтингом, використовуючи метод «бульбашок»;

виводити у списку Lbox_rez ступінь диплома, одержаного переможцем.

Врахуйте, що кількість дипломів розраховується у співвідношенні 1:2:3 від загальної кількості переможців.

1. Завантажте файл-заготовку Вправа_38_2^ із матеріалів до даного параграфа.

У наданому файлі розташовано інтерфейс програми. Елемент Lbox_name містить прізвища переможців. Lbox_grade містить результати 13 переможців, що визначається випадковим числом від 50 до 100.

Створення обробника події для кнопки

2. Створіть команди сортування списку grade за спаданням методом бульбашок. Зауважте, що даний список має стільки ж елементів, скільки і список name.

3. У тілі внутрішнього циклу додайте команду обміну місцями елементів масиву name.

4. Додайте команди очищення елементів керування Lbox_grade та Lbox_name.

5. Додайте команди виведення елементів списків grade та name до елементів Lbox_grade та Lbox_name відповідно.

6. Додайте команду обчислення кількості дипломів першого ступеня:

Із пропорції 1:2:3 неважко здогадатися, що таких дипломів буде шоста частина від загальної кількості призерів. Функція int дозволить одержати цілу частину від ділення.

7. Додайте команду обчислення кількості дипломів другого ступеня:

8. Додайте команду обчислення кількості дипломів третього ступеня. Як правило, дипломи третього ступеня одержують усі призери олімпіади, що не отримали дипломи першого та другого ступенів.

9. Додайте команди виведення напису «І» навпроти учасників, що отримали диплом І ступеня:

10. Додайте команди виведення напису «ІІ» навпроти учасників, що отримали диплом ІІ ступеня.

11. Додайте команди виведення напису «ІІІ» навпроти учасників, що отримали диплом ІІІ ступеня.

12. Додайте команду виклику обробника події.

13. Запустіть програму та перевірте правильність її виконання.

14*. Самостійно змініть код таким чином, аби всі дії в ньому виконувалися при зміні кількості переможців у списку name.

38.2.

Складність алгоритму

При створенні алгоритму програмісти часто кажуть про його складність, швидкодію тощо. Як визначити, який алгоритм є більш складним чи більш швидким? За кількістю команд? Чи є якісь інші критерії визначити це?

Існує декілька способів вимірювання складності алгоритму. Програмісти, як правило, звертають увагу на швидкість алгоритму або об’єм пам’яті, що використовується під час його виконання.

Отже, складність алгоритму — це кількісна характеристика, що відображує споживані алгоритмом ресурси під час свого виконання.

Відповідно складність залежить від розмірів вхідних даних. Звичайно, масив з 10 елементів буде оброблено значно швидше, ніж аналогічний зі 100 елементів.

Часова складність алгоритму характеризується продуктивністю алгоритму, що визначається кількістю елементарних операцій, необхідних для виконання алгоритму. Вважається, що кожна елементарна операція виконується за однаковий час. Часову складність оцінюють для найгіршого випадку і визначають як максимальний час, необхідний для обробки алгоритмом будь-якої множини з n елементів.

Часову складність визначають за виразом O(f(n)). Цей вираз означає, що час роботи алгоритму зростає в залежності від вхідних даних не швидше, ніж деяка константа, помножена на f(n).

38.3.

Поширені складності алгоритмів

0(1) — константна складність.

Час виконання цього алгоритму не залежить від розміру вхідних даних. Проте одиниця у формулі не означає, що алгоритм виконується за одну операцію або потребує дуже мало часу. Він може виконуватися як мікросекунду, так і цілий день.

Наприклад, дано масив цілих чисел. Необхідно визначити кількість елементів масиву.

Алгоритм розв’язання даної задачі буде наступним:

Незалежно від розміру масиву в даному випадку буде виконано дві операції створення масиву та визначення його довжини.

0(n) — лінійна складність

У даному випадку складність алгоритму лінійно зростає при збільшенні вхідних даних. Якщо кількість вхідних даних збільшити у 2 рази, то і час виконання алгоритму буде збільшено у 2 рази. Такі алгоритми легко «впізнати» за наявністю циклу по кожному елементу масиву. Наприклад, обчислення суми парних елементів масиву:

Лінійну складність має також алгоритм сортування масиву вибором, що визначається наявністю одного циклу під час сортування.

0(n²) — квадратична складність

Час роботи такого алгоритму зростає пропорційно квадрату кількості елементів, що обробляються. Отже, при збільшенні вхідних даних у 2 рази, час виконання алгоритму збільшується у 4 рази. Такі алгоритми легко розпізнати за наявністю вкладених циклів. Яскравим прикладом алгоритму, що має квадратичну складність, є сортування масиву методом бульбашок.

ВПРАВА 38.3

Завдання. Створити програми розв’язання задач із вправи 38.3, використовуючи для сортування метод бульбашок.

Контрольні запитання та завдання

1. Опишіть алгоритм сортування методом бульбашок.

2. Якою є складність алгоритму сортування вибором; сортування методом бульбашок?

3. Що таке складність алгоритму?

4. Які існують види складності?

5*. Як змінити команди сортування методом бульбашок за зростанням для сортування цим же методом за спаданням?

Питання для роздумів

1*. Установіть послідовність, в якій змінюється список а=[5, 4, 7, 9, 6] у процесі сортування за спаданням методом бульбашок.

№	0	1	2	3	4
	9	7	6	5	4
	5	4	7	9	6
	7	9	5	6	4
	5	7	9	4	6
	7	5	9	6	4
	5	7	9	6	4
	5	7	4	9	6
	7	9	6	5	4

2*. Яким буде програмний код сортування методом бульбашок, якщо оператор циклу з умовою замінити циклом з параметром?

Завдання для досліджень

1. На сайті youtube.com відшукайте та перегляньте відеоролики, що демонструють різні методи сортування з допомогою танців.

2*. Проаналізуйте алгоритм сортування масиву методом бульбашок із встановленням прапорця flag. Поясніть призначення цього прапорця.

3*. Ознайомтеся із сортуванням методом вставки.

 

 

Це матеріал з підручника Інформатика 9 клас Казанцева, Стеценко 2022