1 of 13

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

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

Урок 53

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

teach-inf.com.ua

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

Бондаренко О.О. та ін.

2 of 13

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

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

Розділ 5

§ 32

3 of 13

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

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

Розділ 5

§ 32

4 of 13

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

Змінна prap типу bool виконує роль прапорця.

Вона отримує значення True в тому випадку, якщо відбулася хоча б одна перестановка сусідніх елементів

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

Розділ 5

§ 32

5 of 13

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

Реалізуємо алгоритм у вигляді функції.

def sort_bulb():

prap = True

k = len(arr)-1

while prap:

prap = False

for i in range(k):

if arr[i]>arr[i+1]:

arr[i], arr[i+1] = arr[i+1], arr[i]

prap = True

k = k-1

Розділ 5

§ 32

6 of 13

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

ПРИКЛАД 2. Проаналізуємо виконання алгоритму на прикладі списку arr = [5, 10, 1, 4, 6].

Перша ітерація зовнішнього циклу, k = 4

5 > 10? Ні

10 > 1? Так. 10 і 1 міняємо місцями, prap = True

10 > 4? Так. 10 і 4 міняємо місцями, prap = True

10 > 6? Так. 10 і 6 міняємо місцями, prap = True

arr = [5, 1, 4, 6, 10]

Розділ 5

§ 32

7 of 13

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

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

Друга ітерація зовнішнього циклу, k = 3

5 > 1? Так. 5 і 1 міняємо місцями, prap = True

5 > 4? Так. 5 і 4 міняємо місцями, prap = True

5 > 6? Ні

arr = [1, 4, 5, 6, 10]

Розділ 5

§ 32

8 of 13

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

(Продовження…) Третя ітерація зовнішнього циклу, k = 2

1 > 4? Ні. prap = False

4 > 5? Ні. prap = False

arr = [1, 4, 5, 6, 10]

Уже на третій ітерації елементи виявились упорядкованими за зростанням, змінна prap = False, тому зовнішній цикл припиняє роботу. Для різних наборів значень списку може знадобитися різна кількість кроків сортування.

Розділ 5

§ 32

9 of 13

Питання для самоперевірки

int(True) = 1; int(False) = 0. Для кожної пари сусідніх елементів списку а виконується операція

s = s+int(a[i] >= a[i+1])

Початкове значення s дорівнює 0. Визначте, чому дорівнює кінцеве значення s, якщо список:

а) було впорядковано за зростанням;

б) було впорядковано за спаданням;

в) не було впорядковано.

Дано список результатів забігу на 100 м восьми спортсменів. Складіть програму для визначення трьох кращих результатів.

Розділ 5

§ 32

10 of 13

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

Бульбашка

Розділ 5

§ 32

11 of 13

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

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

§ 32, с. 189-192

Розділ 5

§ 32

12 of 13

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

Сторінка

191-192

Розділ 5

§ 32

13 of 13

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

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

Урок 53

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

teach-inf.com.ua

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

Бондаренко О.О. та ін.