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

Урок 40

Сьогодні ми дізнаємося

• Навіщо потрібно сортувати дані.
• Як комп'ютер порівнює текст та дати.
• Як працює алгоритм сортування вибором (Selection Sort).
• Як реалізувати сортування на Python без складних функцій.

Урок 40

Навіщо нам сортування?

Уявіть хаос, якщо:

• Контакти в телефоні не за алфавітом.
• В магазині не можна знайти "спочатку дешевші".
• Результати НМТ видані списком без жодного порядку.

Сортування — це впорядкування елементів за певною ознакою (зростання або спадання).

Урок 40

Занотуйте в зошит

Урок 40

Сортування нечислових даних

Комп'ютер порівнює все за кодами символів:

• Текст: порівнюється як у словнику (лексикографічно).
  "Яблуко" > "Абрикос", бо "Я" має більший код.
• Дати: порівнюються хронологічно.
  01.01.2024 < 02.01.2024.
• Логічні значення: False (0) менше за True (1).

Урок 40

Популярні алгоритми

1. Бульбашкою (Bubble Sort): "Легкі" елементи спливають на початок, порівнюючись із сусідами.
2. Вибором (Selection Sort): Ми шукаємо мінімальний елемент і ставимо його на своє місце.

Урок 40

Візуалізація алгоритму вибором

Урок 40

Логіка сортування на Python

Щоб відсортувати список nums довжиною n:

1. Зовнішній цикл i проходить від 0 до n-1.
2. Вважаємо, що nums[i] — це мінімум.
3. Внутрішній цикл j шукає ще менший елемент у залишку списку.
4. Якщо знайшли — міняємо місцями з nums[i].

Урок 40

Реалізація коду

nums = [180, 165, 200, 150, 195]  # Бали НМТ

print("Невпорядковані дані:", nums)

n = len(nums)
for i in range(n):  # Перебираємо елементи списку по черзі
    min_idx = i  # Приймаємо гіпотезу, що поточний елемент вже найменший
    for j in range(i + 1, n):  # Проходимо по решті списку
        if nums[j] < nums[min_idx]:  # Якщо знайшли менше значення
            min_idx = j  # Запам'ятовуємо його номер

    # Обмінюємо значення місцями
    current_value = nums[i]  # Зберігаємо значення на поточному місці
    min_value = nums[min_idx]  # Зберігаємо найменше знайдене значення

    nums[i] = min_value  # Ставимо найменше значення на поточне місце
    nums[min_idx] = current_value  # Ставимо поточне значення на місце найменшого

print("Впорядковані дані:", nums)

Урок 40

Практичне завдання