1 of 28

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

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

Урок 55

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

teach-inf.com.ua

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

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

2 of 28

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

Як визначити найбільший і найменший елементи одновимірного масиву?

Як обміняти місцями значення двох змінних?

Як ви розумієте поняття «Складність задачі»?

Розділ 5

§ 5.3

3 of 28

Впорядковані одновимірні масиви

Одновимірний масив вважається впорядкованим, якщо серед значень його елементів встановлено певний порядок. Наведемо кілька прикладів впорядкованих одновимірних масивів:

список учнів вашого класу на кожній сторінці класного журналу впорядкований в алфавітному порядку;

список слів в орфографічному або тлумачному словнику також впорядковані в алфавітному порядку;

Розділ 5

§ 5.3

4 of 28

Впорядковані одновимірні масиви

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

список номерів автобусних маршрутів і відомостей про кожний з них впорядкований за зростанням номерів маршрутів;

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

Розділ 5

§ 5.3

5 of 28

Впорядковані одновимірні масиви

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

підсумкова таблиця чемпіонату України з футболу впорядкована за спаданням кількості набраних очок: від найбільшої кількості набраних очок до найменшої (при рівності набраних очок таблицю впорядковують за додатковими критеріями)

Розділ 5

§ 5.3

6 of 28

Впорядковані одновимірні масиви

Розрізняють 4 види впорядкованості одновимірного масиву за значеннями його елементів:

Зростанням

Неспаданням

Спаданням

Незростанням

якщо значення елементів не повторюються

якщо значення елементів можуть повторюватись

Розділ 5

§ 5.3

7 of 28

Впорядковані одновимірні масиви

Одновимірний масив a називається впорядкованим за зростанням (зростаючим), якщо значення кожного його наступного елемента більше значення попереднього, тобто для всіх і виконується нерівність:

a[i+1] > a[i]

Наприклад, впорядкованим за зростанням (зростаючим) є масив:

5; 12; 32; 44,5; 88; 101

Розділ 5

§ 5.3

8 of 28

Впорядковані одновимірні масиви

Одновимірний масив a називається впорядкованим за спаданням (спадним), якщо значення кожного його наступного елемента менше значення попереднього, тобто для всіх і виконується нерівність:

a[i+1] < a[i]

Наприклад, впорядкованим за спаданням (спадним) є масив:

45; 32; 22; 4,5; 0; –7

Розділ 5

§ 5.3

9 of 28

Впорядковані одновимірні масиви

Одновимірний масив a називається впорядкованим за неспаданням (неспадним), якщо значення кожного його наступного елемента не менше (більше або дорівнює) значення попереднього, тобто для всіх і виконується нерівність:

a[i+1] ≥ a[i]

Наприклад, впорядкованим за неспаданням (неспадним) є масив:

15; 22; 22; 34; 40; 40

Розділ 5

§ 5.3

10 of 28

Впорядковані одновимірні масиви

Одновимірний масив a називається впорядкованим за незростанням (незростаючим), якщо значення кожного його наступного елемента не більше (менше або дорівнює) значення попереднього, тобто для всіх і виконується нерівність:

a[i+1] ≤ a[i]

Наприклад, впорядкованим за незростанням (незростаючим) є масив:

35; 12; 12; 7; 7; 1

Розділ 5

§ 5.3

11 of 28

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

Таких алгоритмів існує досить багато. Ми розглянемо два з них:

Алгоритми перетворення невпорядкованих одновимірних масивів у впорядковані називаються алгоритмами впорядкування (сортування) одновимірних масивів.

впорядкування

методом вибору

впорядкування

методом обміну

Розділ 5

§ 5.3

12 of 28

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

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

23	7	4	16	-2	10

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

Нехай маємо такий одновимірний масив з 6 чисел. Він невпорядкований.

Розділ 5

§ 5.3

13 of 28

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

Виберемо найменший елемент масиву (це – число -2)

23	7	4	16	-2	10

Обміняємо його місцями з першим елементом масиву.

-2	7	4	16	23	10

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

Розділ 5

§ 5.3

14 of 28

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

Виберемо найменший елемент невпорядкованої частини масиву (це – число 4)

Обміняємо його місцями з першим елементом невпорядкованої частини масиву (це – число 7).

-2	4	7	16	23	10

Отримаємо масив, у якому перші два елементи масиву впорядковані за зростанням. Тобто вони вже зайняли своє місце в майбутньому впорядкованому масиві:

-2	7	4	16	23	10

Розділ 5

§ 5.3

15 of 28

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

Знову виберемо найменший елемент невпорядкованої частини масиву (це – число 7)

Обміняємо його місцями з першим елементом невпорядкованої частини масиву (це в даному випадку – те саме число 7).

-2	4	7	16	23	10

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

-2	4	7	16	23	10

Розділ 5

§ 5.3

16 of 28

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

Ще раз виберемо найменший елемент невпорядкованої частини масиву (це – число 10) і обміняємо його місцями з першим елементом невпорядкованої частини масиву (це – число 16). Отримаємо такий масив:

-2	4	7	10	23	16

В якому перші чотири елементи зайняли своє місце в майбутньому впорядкованому масиві.

Ще один раз виконаємо ці операції, і отримаємо впорядкований за зростанням одновимірний масив:

-2	4	7	10	16	23

Розділ 5

§ 5.3

17 of 28

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

Отже, ми мали одновимірний масив з 6 чисел. І ми 5 разів виконували такі дії:

Вибирали найменший елемент серед елементів поки що невпорядкованої частини масиву.

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

Звертаємо вашу увагу, що на останньому кроці виконання алгоритму свої місця зайняли одразу два елементи масиву.

Розділ 5

§ 5.3

18 of 28

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

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

a = list(map(float, input

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

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

for i in range(5): # 5 разів повторюємо

min = a[i] # перший елемент невпорядкованої

# поки що частини списку вважаємо найменшим

nmin = i # номер першого елемента невпорядкованої

# поки що частини списку вважаємо номером

# найменшого

Розділ 5

§ 5.3

19 of 28

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

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

for j in range(i+1, 6): # переглядаємо елементи списку,

# починаючи з наступ ного і до останнього, можливо

# серед них є менший, ніж той, який ми на даний

# момент вважаємо найменшим у невпорядкованій

# частині

if a[j]<min: # якщо зустрічається елемент, менший ніж

# той, який ми вважаємо найменшим у

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

# найменшим і його номер стає номером найменшого

min = a[j]

nmin = j

Розділ 5

§ 5.3

20 of 28

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

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

a[nmin] = a[i] # на місце знайденого найменшого

# елемента невпорядкованої поки що

# частини списку ставимо перший елемент

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

a[i] = min # на місце першого елемента

# невпорядкованої поки що частини списку

# ставимо знайдений найменший

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

Розділ 5

§ 5.3

21 of 28

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

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

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

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

Розділ 5

§ 5.3

22 of 28

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

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

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

Переконайтеся в цьому разом з однокласником/

однокласницею на прикладі масиву:

12; 4; 6; 2; 6; 4.

Розділ 5

§ 5.3

23 of 28

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

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

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

youtu.be/Ns4TPTC8whw

toptal.com/developers/

sorting-algorithms

Розділ 5

§ 5.3

24 of 28

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

Який одновимірний масив вважається впорядкованим? Наведіть приклади.

Які ви знаєте 4 види впорядкованості одновимірного масиву? Наведіть приклади.

Який одновимірний масив називається впорядкованим за зростанням? Наведіть приклади.

Який одновимірний масив називається впорядкованим за спаданням?

Який одновимірний масив називається впорядкованим за неспаданням?

Розділ 5

§ 5.3

25 of 28

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

Сортування

Розділ 5

§ 5.3

26 of 28

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

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

§ 5.3, с. 258-262

Розділ 5

§ 5.3

27 of 28

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

Сторінка

267-268

Розділ 5

§ 5.3

28 of 28

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

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

Урок 55

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

teach-inf.com.ua

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

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