Алгоритми впорядкування масиву
👩🏫Методичні акценти для вчителя • План проведення уроку на 45 хвНУШ▼
🎯 Очікувані результати навчання (НУШ):
Формування предметних компетентностей за темою «Алгоритми впорядкування масиву», розвиток критичного мислення, вміння аналізувати причинно-наслідкові зв'язки та застосовувати набуті знання на практиці.
💬 Провокативне питання для старту:
Використайте блок «Гачок (Hook)» нижче для 2-хвилинної розминки з класом перед поясненням нового матеріалу.
⏱️ Рекомендований таймінг 45-хвилинного уроку:
Тема: § 29. Алгоритми впорядкування масиву. Д/з: опрацювати матеріал уроку та завдання «У зошит» на платформі EZZ-SCHOOL BOOKS.
⚡ Фронтальне бліц-опитування класу на початку уроку (2 хв):
- Що є ключовим поняттям теми «Алгоритми впорядкування масиву» і чому воно важливе?
- Де у повсякденному житті, науці чи IT ми стикаємося з цим явищем/алгоритмом?
- Яка найпоширеніша помилка виникає під час першого знайомства з матеріалом?
🏠 Диференційоване домашнє завдання:
- Базовий рівень (обов'язковий): опрацювати конспект і блок «У зошит».
- Достатній рівень: скласти власну шпаргалку та пройти MiniCheck.
- Високий / STEM: виконати симуляцію у лабораторії та скласти BossQuiz на 100 XP.
📊 Критерії формувального оцінювання:
Твоя місія на цей урок
Натискай на цілі у міру їх опанування:
- 1Зрозуміти логіку та математичну суть алгоритмів сортування даних.Опанувати ➔
- 2Реалізувати алгоритм сортування бульбашкою (Bubble Sort) на Python.Опанувати ➔
- 3Опанувати алгоритм сортування вибором (Selection Sort).Опанувати ➔
- 4Застосовувати елегантний синтаксис обміну двох змінних кортежем: a, b = b, a.Опанувати ➔
💡 Чому сортування — це фундаментальна задача комп'ютерних наук?
Шукати слово у несортованому словнику — це перегортати всі сторінки підряд до вечора. Але якщо слова розставлені за абеткою, ви знаходите потрібне за 3 секунди! Близько 25% усього процесорного часу світових серверів витрачається саме на впорядкування даних: постів, цін, рейтингів і пошукових запитів.
1. Чому сортування — основа комп'ютерних наук?
У несортованому масиві з $N$ елементів пошук потрібного значення потребує перегляду всіх елементів ($O(N)$ операцій). Якщо ж масив відсортований, алгоритм бінарного пошуку знаходить запис серед 1 000 000 000 елементів всього за 30 порівнянь ($O(\log_2 N)$)! Саме тому швидкі алгоритми сортування лежать в основі всіх пошукових систем Google та баз даних.
Сортування бульбашкою
Найпростіший для розуміння алгоритм: сусідні елементи порівнюються та «спливають» праворуч.
Сортування вибором
Шукає мінімальний елемент серед несортованої частини та ставить його на початок.
Сортування вставками
Бере наступний елемент і вставляє його в уже відсортовану ліву частину, як гральні карти в руці.
Метод Бульбашки vs Сортування Вибором
Керування покроковим виконанням:
💡 Бульбашка: Порівнюються дві сусідні клітинки. Якщо ліва більша за праву — міняємо місцями. За кожен повний прохід найбільше число спливає в кінець масиву.
n = len(a)
for i in range(n - 1):
for j in range(n - 1 - i):
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j] # Обмін кортежем2. Алгоритм сортування бульбашкою (Bubble Sort)
Алгоритм порівнює пари сусідніх елементів a[j] та a[j+1]. Якщо лівий більший за правий — вони міняються місцями (swap). За один повний прохід найбільший елемент гарантовано спливає у самий кінець списку:
Оптимізований код мовою Python:
def bubble_sort(a):
n = len(a)
for i in range(n - 1):
swapped = False
for j in range(n - 1 - i):
if a[j] > a[j + 1]:
# Обмін місцями в Python без третьої змінної:
a[j], a[j + 1] = a[j + 1], a[j]
swapped = True
# Якщо за весь прохід не було жодного обміну — список уже відсортований!
if not swapped:
break
return a3. Сортування вибором (Selection Sort)
На кожній ітерації $i$ знаходиться індекс найменшого елемента в діапазоні від $i$ до кінця списку, після чого цей мінімум міняється місцями з елементом $a[i]$:
def selection_sort(a):
n = len(a)
for i in range(n - 1):
min_idx = i
for j in range(i + 1, n):
if a[j] < a[min_idx]:
min_idx = j
a[i], a[min_idx] = a[min_idx], a[i]
return a| Алгоритм | Найкращий час | Найгірший час | Пам'ять |
|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(1) |
| Selection Sort | O(n²) | O(n²) | O(1) |
| Timsort (вбудований .sort()) | O(n) | O(n log n) | O(n) |
🎯 Міні-тест: обмін елементів
Як у мові Python правильно поміняти місцями два сусідні елементи списку a[j] та a[j+1] в один рядок?
Оберіть правильний рядок коду:
У зошит (за підручником)
Вправи з підручника до цієї теми уроку. Виконуй у робочий зошит або за комп'ютером за вказівкою вчителя:
Реалізація алгоритму бульбашки та сортування вибором
💡 Підказка від нас: Написати програму, яка генерує список із 8 випадкових чисел від 1 до 50, впорядковує його методом бульбашки з виведенням кількості виконаних перестановок.
Шпаргалка уроку (головне в один екран)
Усе найважливіше для повторення перед уроком або самостійною роботою
for i in range(n - 1):
for j in range(n - 1 - i):
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]- a.sort() — за зростанням
- a.sort(reverse=True) — за спаданням
- b = sorted(a) — копія без зміни a
Бос-тест: Алгоритми сортування масивів
Питання 1 з 3 • Завдай удару по босу теми