Л8. Сортування та поділ задачі на менші частини

Коротко про лекцію

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

У Л7 впорядкованість була передумовою швидкого пошуку. Тепер треба зрозуміти, звідки вона береться, скільки роботи потребує сортування та як ідея поділу задачі пов’язана з рекурсивними викликами.

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

1. Що означає «відсортувати»

Нехай маємо значення:

7, 3, 9, 2

Для сортування за зростанням очікуємо:

2, 3, 7, 9

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

Це можна перевірити локальним правилом:

values.at(0) <= values.at(1)
values.at(1) <= values.at(2)
values.at(2) <= values.at(3)

Для довшої послідовності такий самий принцип перевіряє кожну сусідню пару.

2. Сортування вибором починається з найменшого елемента

Розглянемо простий алгоритм, який легко трасувати вручну.

Перший крок:

1. знайти найменший елемент у всій послідовності;
2. поміняти його місцями з першим елементом.

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

Так працює сортування вибором.

flowchart TD
    A["7, 3, 9, 2"] --> B["Знайти мінімум: 2"]
    B --> C["Поміняти 7 і 2 місцями"]
    C --> D["2, 3, 9, 7"]
    D --> E["Перша позиція готова"]
    E --> F["Повторити для решти"]

2.1. Обмін двох значень

Для перестановки двох елементів стандартна бібліотека має функцію std::swap(a, b). Вона міняє значення двох об’єктів місцями.

Для неї підключимо заголовок:

#include <utility>

Тепер виконаємо лише перший крок сортування.

#include <iostream>
#include <utility>
#include <vector>

int main() {
    std::vector<int> values{7, 3, 9, 2};
    std::size_t smallest{0};

    // Після циклу smallest має вказувати на найменший елемент у всій послідовності.
    for (std::size_t i{1}; i < values.size(); ++i) {
        if (values.at(i) < values.at(smallest)) {
            smallest = i;
        }
    }

    // Перший прохід завершується перенесенням знайденого мінімуму на початок.
    std::swap(values.at(0), values.at(smallest));

    for (int value : values) {
        std::cout << value << ' ';
    }
    std::cout << "\n";
}

Після першого проходу отримуємо 2 3 9 7. Перша позиція вже остаточна, а решта ще може бути невпорядкованою.

2.2. Інваріант готової частини

Після кожного зовнішнього кроку зліва з’являється частина, яку більше не треба змінювати.

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

Термін: інваріант

Інваріант — властивість, яка залишається істинною у визначених точках алгоритму. Вона допомагає пояснити, чому кожний крок зберігає вже досягнуту правильність.

Для сортування вибором інваріант можна сформулювати так:

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

Інваріант допомагає пояснити, чому алгоритм поступово наближається до готового результату.

3. Повне сортування вибором має два вкладені проходи

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

Сортування повинно змінити std::vector, який передав виклик. У Л6 ми вже використовували const& для читання наявного std::vector. Тепер функції потрібен доступ до змін, тому const прибираємо, а & залишаємо.

Запис std::vector<int>& values означає змінюване посилання. Параметр values стає другим ім’ям переданого std::vector. Тому заміна елемента через values змінює початкову послідовність.

Тип void означає функцію без поверненого значення. У наступному прикладі результатом функції є зміна переданого std::vector.

Мінімальна форма виглядає так:

void set_first_to_zero(std::vector<int>& values) {
    if (values.size() > 0) {
        values.at(0) = 0;
    }
}

Тому заголовок сортування має форму:

void selection_sort(std::vector<int>& values)

Під час сортування всі перестановки через values працюють з початковою послідовністю. Це дає функції змогу впорядкувати std::vector викликача.

#include <iostream>
#include <utility>
#include <vector>

void selection_sort(std::vector<int>& values) {
    // Перед позицією start уже стоять найменші елементи в остаточному порядку.
    for (std::size_t start{0}; start < values.size(); ++start) {
        std::size_t smallest{start};

        for (std::size_t i{start + 1}; i < values.size(); ++i) {
            if (values.at(i) < values.at(smallest)) {
                smallest = i;
            }
        }

        // Поточний мінімум займає start і більше не потребує перестановок.
        std::swap(values.at(start), values.at(smallest));
    }
}

int main() {
    std::vector<int> values{7, 3, 9, 2};
    selection_sort(values);

    for (int value : values) {
        std::cout << value << ' ';
    }
    std::cout << "\n";
}

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

Крок	Готова позиція	Стан std::vector після обміну
1	0	2, 3, 9, 7
2	1	2, 3, 9, 7
3	2	2, 3, 7, 9
4	3	2, 3, 7, 9

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

4. Два вкладені проходи створюють квадратичне зростання роботи

У Л7 ми ввели O-нотацію через кількість порівнянь. Для сортування вибором основною роботою знову можна вважати порівняння елементів.

Для п’яти елементів кількість порівнянь:

4 + 3 + 2 + 1 = 10

#include <iostream>
#include <vector>

int selection_comparisons(const std::vector<int>& values) {
    // Значення елементів не впливають на кількість цих порівнянь для заданого розміру.
    int comparisons{0};

    for (std::size_t start{0}; start < values.size(); ++start) {
        for (std::size_t i{start + 1}; i < values.size(); ++i) {
            ++comparisons;
        }
    }

    return comparisons;
}

int main() {
    const std::vector<int> values{8, 1, 6, 2, 5};
    std::cout << selection_comparisons(values) << "\n";
}

Якщо розмір входу позначити n, сума має порядок n². Тому сортування вибором має квадратичне зростання O(n²).

Термін: O(n²)

O(n²) означає квадратичний порядок зростання роботи. Подвоєння n наближено множить домінантну кількість операцій на чотири.

Практично це означає: якщо збільшити розмір приблизно вдвічі, обсяг порівнянь зросте приблизно в чотири рази.

n	Порівнянь у сортуванні вибором
10	45
100	4 950
1000	499 500

flowchart LR
    A["n"] --> B["зовнішній цикл ≈ n кроків"]
    B --> C["внутрішній пошук ≈ n перевірок"]
    C --> D["разом порядок n²"]

5. Для звичайного сортування використовуємо готовий алгоритм бібліотеки

Ручне сортування вибором корисне для розуміння інваріанта та вартості вкладених проходів. У прикладній програмі для звичайного впорядкування std::vector доцільно використовувати std::sort.

std::sort знаходиться у заголовку:

#include <algorithm>

Функції треба передати початок і кінець діапазону. Методи begin() і end() повертають об’єкти-позиції. Такі об’єкти називають ітераторами.

Термін: ітератор

Ітератор позначає позицію в послідовності та дає алгоритму спосіб рухатися між елементами. На цьому етапі достатньо читати begin() як початок, а end() — як позицію одразу після останнього елемента.

Як читати begin() і end()

Діапазон стандартних алгоритмів має форму [begin, end). Початкова позиція входить до діапазону, а позиція end() уже лежить за останнім елементом.

Тому весь std::vector передаємо так:

std::sort(values.begin(), values.end());

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> values{7, 3, 9, 2};
    std::sort(values.begin(), values.end());

    for (int value : values) {
        std::cout << value << ' ';
    }
    std::cout << "\n";
}

Для великих даних стандартне сортування має значно кращий характер зростання, приблизно O(n log n) порівнянь. Множник log n зростає повільно, тому цей порядок значно кращий за n² на великих входах.

5.1. Навіщо тоді вивчати прості сортування

Сортування вибором показує три важливі ідеї:

1. як формується інваріант готової частини;
2. як вкладені цикли впливають на обсяг роботи;
3. як відділяти навчальний алгоритм від інструмента для прикладного коду.

Для реальної програми обираємо перевірений стандартний алгоритм, якщо задача не вимагає спеціальної поведінки.

6. Функція може викликати саму себе

До цього моменту одна функція викликала іншу. Іноді задача має однакову структуру на меншому розмірі. Тоді функція може викликати саму себе з меншим аргументом.

Такий спосіб називають рекурсією.

Термін: рекурсія

Рекурсія — спосіб розв’язання, у якому функція викликає себе для меншої задачі того самого типу. Коректна рекурсія має шлях до завершення.

Рекурсивна функція повинна мати дві частини:

1. базовий випадок — найменша задача, яку можна розв’язати без нового виклику;
2. рекурсивний крок — перехід до меншої задачі того самого типу.

Для суми 1 + 2 + ... + n можна використати співвідношення:

sum_to(0) = 0
sum_to(n) = n + sum_to(n - 1), якщо n > 0

Базовий випадок n == 0 зупиняє подальші виклики.

Термін: базовий випадок

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

#include <iostream>

int sum_to(int n) {
    // Базовий випадок зупиняє рекурсію; без нього виклики не завершилися б.
    if (n == 0) {
        return 0;
    }
    return n + sum_to(n - 1);
}

int main() {
    std::cout << sum_to(4) << "\n";
}

Для sum_to(4) виклики утворюють:

4 + sum_to(3)
4 + 3 + sum_to(2)
4 + 3 + 2 + sum_to(1)
4 + 3 + 2 + 1 + sum_to(0)

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

7. Стек викликів зберігає незавершені функції

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

Стек викликів — це структура, де зберігаються активні виклики функцій. Новий виклик додається зверху. Після завершення він прибирається, і виконання повертається до попереднього.

Термін: стек викликів

Стек викликів зберігає стан незавершених викликів. Рекурсія додає новий запис для кожного вкладеного виклику, тому глибина рекурсії впливає на пам’ять.

Подивимося на функцію, яка друкує повідомлення до і після рекурсивного виклику.

Тут знову використаємо вже введений тип результату void: countdown виконує виведення та не повертає окремого значення.

#include <iostream>

void countdown(int n) {
    // Повідомлення до і після рекурсивного виклику показують порядок роботи стеку викликів.
    std::cout << "Вхід: " << n << "\n";

    if (n > 0) {
        countdown(n - 1);
    }

    std::cout << "Вихід: " << n << "\n";
}

int main() {
    countdown(3);
}

Порядок виведення показує дві фази: спуск до базового випадку та повернення назад.

sequenceDiagram
    participant C3 as countdown(3)
    participant C2 as countdown(2)
    participant C1 as countdown(1)
    participant C0 as countdown(0)
    C3->>C2: виклик
    C2->>C1: виклик
    C1->>C0: виклик
    C0-->>C1: завершення
    C1-->>C2: завершення
    C2-->>C3: завершення

7.1. Базовий випадок є умовою завершення

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

Наприклад, sum_to(n + 1) рухався б у неправильному напрямку. Такий код не наближається до n == 0.

Перед запуском рекурсивної функції треба відповісти на два питання:

1. який базовий випадок завершує виклики;
2. чому кожний рекурсивний крок наближається до нього.

8. Поділ задачі на частини може працювати рекурсивно

У Л7 двійковий пошук щоразу залишав половину діапазону. Це приклад ширшої ідеї: велику задачу можна розділити на менші підзадачі, розв’язати їх і поєднати результати.

Цей підхід називають методом «поділяй і володарюй».

Типова схема:

велика задача
→ поділити на менші частини
→ розв’язати частини
→ поєднати результати

Для суми діапазону можна розділяти відрізок індексів навпіл.

flowchart TD
    A["0..3"] --> B["0..1"]
    A --> C["2..3"]
    B --> D["0"]
    B --> E["1"]
    C --> F["2"]
    C --> G["3"]
    D --> H["сума лівої частини"]
    E --> H
    F --> I["сума правої частини"]
    G --> I
    H --> J["загальна сума"]
    I --> J

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

#include <iostream>
#include <vector>

int range_sum(const std::vector<int>& values, int left, int right) {
    // Один елемент уже є готовою сумою і зупиняє подальший поділ.
    if (left == right) {
        return values.at(static_cast<std::size_t>(left));
    }

    // Більший діапазон ділимо на дві частини, а потім об’єднуємо їхні суми.
    const int middle{left + (right - left) / 2};
    const int left_sum{range_sum(values, left, middle)};
    const int right_sum{range_sum(values, middle + 1, right)};
    return left_sum + right_sum;
}

int main() {
    const std::vector<int> values{2, 4, 6, 9};
    std::cout << range_sum(values, 0, 3) << "\n";
}

Цей приклад не є найпростішим способом знайти суму std::vector. Його роль — показати механіку рекурсивного поділу діапазону.

9. Рекурсія має ціну

Кожний активний рекурсивний виклик займає місце у стеку викликів. Дуже глибока рекурсія може використати надто багато стекової пам’яті.

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

Для простого проходу std::vector цикл часто читається простіше. Для дерев, рекурсивних структур і алгоритмів поділу рекурсія може прямо відображати структуру задачі.

Вибір конструкції випливає з форми алгоритму.

10. Сортування, пошук і поділ задачі пов’язані

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

flowchart TD
    A["Невпорядковані дані"] --> B["Сортування"]
    B --> C["Впорядковані дані"]
    C --> D["Двійковий пошук"]
    D --> E["На кожному кроці відкидаємо половину"]

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

11. Як перевіряти сортування і рекурсію

Для сортування перевірте:

1. порожню послідовність;
2. один елемент;
3. уже відсортовані значення;
4. зворотний порядок;
5. повторювані значення.

Для рекурсії перевірте:

1. базовий випадок;
2. найменший випадок, який робить один рекурсивний крок;
3. кілька рівнів викликів;
4. напрямок наближення до базового випадку.

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

12. Інтерактивна самоперевірка лекції

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