1 of 22

Алгоритми впорядкування масиву

За навчальною програмою 2017 року

Урок 56

Інформатика 9

teach-inf.com.ua

за підручником

Ривкінд Й.Я. та ін.

2 of 22

Впорядкування одновимірного масиву�методом обміну

Розглянемо алгоритм впорядкування одновимірного масиву методом обміну. Будемо, як і в попередньому алгоритмі, впорядковувати масив за зростанням.

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

13	6	5	18	11	10

Братимемо по черзі два сусідні елементи масиву (перший і другий, другий і третій, третій і четвертий і т.д.) і, якщо лівий з них більше правого, обмінюватимемо їх місцями.

Розділ 5

§ 5.3

3 of 22

Впорядкування одновимірного масиву�методом обміну

Беремо перший і другий елементи масиву: 13 і 6, 13>6, тому обмінюємо їх місцями і отримаємо такий масив:

6	13	5	18	11	10

Беремо другий і третій елементи масиву: 13 і 5, 13>5, тому обмінюємо їх місцями і отримаємо такий масив:

6	5	13	18	11	10

Розділ 5

§ 5.3

4 of 22

Впорядкування одновимірного масиву�методом обміну

Беремо третій і четвертий елементи масиву: 13 і 18, 13 не більше 18, тому не обмінюємо їх місцями і масив залишається той самий.

Беремо четвертий і п’ятий елементи масиву: 18 і 11, 18>11, тому обмінюємо їх місцями і отримаємо такий масив:

6	5	13	11	18	10

Беремо п’ятий і шостий елементи масиву: 18 і 10, 18>10, тому обмінюємо їх місцями і отримаємо такий масив:

6	5	13	11	10	18

Розділ 5

§ 5.3

5 of 22

Впорядкування одновимірного масиву�методом обміну

У результаті першого проходу по масиву найбільший елемент масиву стає останнім і займає своє місце в майбутньому впорядкованому масиві. Тому в подальшому впорядкуванні попередній до нього елемент порівнювати з ним вже не потрібно.

Далі потрібно повторити цей процес, починаючи з першого елемента масиву.

Тоді після другого проходу по масиву два останні елементи займуть свої місця в майбутньому впорядкованому масиві:

5	6	11	10	13	18

Розділ 5

§ 5.3

6 of 22

Впорядкування одновимірного масиву�методом обміну

І так далі.

5	6	10	11	13	18

Усього потрібно зробити 5 проходів по масиву. На останньому проході свої місця займуть одразу два елементи. Після чого отримаємо впорядкований за зростанням масив.

Розділ 5

§ 5.3

7 of 22

Впорядкування одновимірного масиву�методом обміну

Складемо фрагмент проєкту для впорядкування за зростанням одновимірного масиву з 6 дійсних чисел, що вводяться з клавіатури, методом обміну.

a = list(map(float, input

('Уведіть 6 чисел через пропуск > ').split()))

# уведення значень елементів списку з 6 дійсних чисел

for i in range(5): # 5 разів повторюємо прохід по списку

for j in range(5-i): # порівнюємо кожну пару сусідніх елементів

# від першого елементу масиву до останнього у

# невпорядкованій частині масиву

Розділ 5

§ 5.3

8 of 22

Впорядкування одновимірного масиву�методом обміну

Продовження…

if a[j]>a[j+1]: # якщо лівий з двох сусідніх елементів

# більше правого з них

x = a[j] # обмінюємо два сусідні елементи місцями,

# використовуючи допоміжну змінну х

a[j] = a[j+1]

a[j+1] = x

print(a) # виведення впорядкованого списку

Розділ 5

§ 5.3

9 of 22

Впорядкування одновимірного масиву�методом обміну

Звертаємо вашу увагу:

Щоб впорядкувати одновимірний масив за спаданням, потрібно при порівнянні двох сусідніх елементів обмінювати їх місцями у тому випадку, якщо лівий з них менше правого з них.

Для цього необхідно внести певні зміни у фрагмент проєкту. Обговоріть з однокласником/однокласницею

які саме.

Розділ 5

§ 5.3

10 of 22

Впорядкування одновимірного масиву�методом обміну

Продовження…

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

12; 4; 6; 2; 6; 4

Розділ 5

§ 5.3

11 of 22

Впорядкування одновимірного масиву�методом обміну

Продовження…

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

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

Розділ 5

§ 5.3

12 of 22

Впорядкування одновимірного масиву�методом обміну

Продовження…

Метод обміну інколи називають методом «бульбашки». За аналогією з тим, як бульбашки в газованій воді спливають на поверхню,

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

Розділ 5

§ 5.3

13 of 22

Впорядкування одновимірного масиву�методом обміну

Продовження…

В Інтернеті можна подивитися візуалізацію методу обміну, наприклад, за адресами:

youtu.be/lyZQPjUT5B4

toptal.com/developers/

sorting-algorithms

Розділ 5

§ 5.3

14 of 22

Які методи упорядкування можна використати в мові програмування Python?

У мові програмування Python для сортування списку використовують метод.

За замовчуванням метод сортує елементи списку в порядку зростання значень. Метод може змінити порядок сортування за допомогою таких іменованих аргументів:

sort ()

аргумент, який дає змогу визначити власну функцію порівняння при виклику методу sort (). Ця функція отримує один єдиний аргумент і повертає значення, яке буде використовуватися в операції порівняння;

key

Розділ 5

§ 5.3

15 of 22

Які методи упорядкування можна використати в мові програмування Python?

Продовження…

аргумент, який використовується для вказівки порядку сортування елементів.

Якщо reverse = True, то елементи списку сортуються в порядку спадання.

reverse

Розділ 5

§ 5.3

16 of 22

Які методи упорядкування можна використати в мові програмування Python?

Програмний код

Результат

А = ['a', 'b', 'd', 'f', 'n', 'v']

В = [1, 2, 3, 5, 8, 10]

Розділ 5

§ 5.3

17 of 22

Які методи упорядкування можна використати в мові програмування Python?

Для зміни порядку елементів списку на зворотній у вже відсортованому списку використовують метод реверсування списку reverse ().

Програмний код

Результат

A = [5, 4, 3, 2, 1]

B = ['a', 'b', 'c', 'd', 'е', 'f']

Розділ 5

§ 5.3

18 of 22

Дайте відповіді на запитання

У чому полягає суть алгоритму впорядкування одновимірного масиву методом вибору?

У чому полягає суть алгоритму впорядкування одновимірного масиву методом обміну?

Розділ 5

§ 5.3

19 of 22

Розгадайте ребус

Бульбашка

Розділ 5

§ 5.3

20 of 22

Домашнє завдання

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

§ 5.3, с. 262-265

Розділ 5

§ 5.3

21 of 22

Працюємо за комп’ютером

Сторінка

268

Розділ 5

§ 5.3

22 of 22

Дякую за увагу!

За навчальною програмою 2017 року

Урок 56

Інформатика 9

teach-inf.com.ua

за підручником

Ривкінд Й.Я. та ін.