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

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

Сортування — одна з найбільш фундаментальних і досліджуваних задач в інформатиці. Не тому що воно рідко зустрічається в реальному житті (навпаки — воно всюди: ранжування у пошуку, стрічки соціальних мереж, ціни в інтернет-магазині), а тому що пошук ефективного способу впорядкувати дані навчив людство думати про складність алгоритмів.

Кожен алгоритм сортування — це маленький філософський трактат: «Яку ціну ми платимо за порядок?» Різні алгоритми відповідають на це питання по-різному. Один витрачає менше порівнянь, інший — менше переміщень, третій краще працює на майже-відсортованих даних. Щоб порівнювати algorithms чесно, нам потрібна єдина мова вимірювання — і ця мова називається Big O.

Big O нотація: мова складності

Проблема вимірювання

Як виміряти швидкість алгоритму? Перше, що спадає на думку — засікти час виконання на комп'ютері. Але це поганий підхід: час залежить від процесора, оперативної пам'яті, поточного навантаження системи, компілятора, оптимізацій. Один і той самий алгоритм на старому ноутбуці займе 5 секунд, на сервері — 0.1 секунди. Як же порівнювати?

Відповідь: вимірювати не час, а кількість операцій — і залежність цієї кількості від розміру вхідних даних.

Big O нотація (нотація «О велике») — математична мова для опису цієї залежності. Вона показує, як зростає час (або пам'ять) алгоритму при збільшенні розміру вхідних даних n — у найгіршому випадку.

Основні класи складності

Розглянемо основні класи Big O від найшвидшого до найповільнішого:

graph LR
    A["O(1)\nКонстантна"] --> B["O(log n)\nЛогарифмічна"]
    B --> C["O(n)\nЛінійна"]
    C --> D["O(n log n)\nЛінійно-логарифмічна"]
    D --> E["O(n²)\nКвадратична"]
    E --> F["O(2ⁿ)\nЕкспоненційна"]

    style A fill:#22c55e,stroke:#16a34a,color:#ffffff
    style B fill:#3b82f6,stroke:#1d4ed8,color:#ffffff
    style C fill:#f59e0b,stroke:#b45309,color:#ffffff
    style D fill:#f97316,stroke:#ea580c,color:#ffffff
    style E fill:#ef4444,stroke:#dc2626,color:#ffffff
    style F fill:#7c3aed,stroke:#6d28d9,color:#ffffff

O(1) — Константна складність. Кількість операцій не залежить від розміру вхідних даних. Незалежно від того, скільки елементів у масиві — дія завжди займає однаковий час.

int firstElement = arr[0];  // Завжди одна операція

O(log n) — Логарифмічна складність. З кожною операцією задача вдвічі зменшується. Бінарний пошук у відсортованому масиві: шукаємо серед 1 000 000 елементів — потрібно не більше 20 порівнянь (бо 2²⁰ ≈ 1 000 000).

O(n) — Лінійна складність. Кількість операцій прямо пропорційна розміру вхідних даних. Пошук у невідсортованому масиві: в найгіршому випадку потрібно перевірити кожен елемент.

for (int i = 0; i < n; i++) { /* одна операція */ }  // O(n)

O(n log n) — Лінійно-логарифмічна складність. «Золотий стандарт» порівняльного сортування. Швидке сортування та сортування злиттям. Значно ефективніший за O(n²) на великих даних.

O(n²) — Квадратична складність. Два вкладені цикли на одних і тих самих даних. Прийнятна на малих масивах (до кількох тисяч елементів), але катастрофічна на великих: мільйон елементів → 10¹² операцій.

for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) { /* одна операція */ }  // O(n²)

Наочне порівняння: що відбувається при n = 1 000 000?

Ця таблиця пояснює, чому вибір алгоритму критично важливий. Різниця між O(n log n) та O(n²) — це різниця між «20 мілісекунд» та «17 хвилин» на одному мільйоні елементів.

Best, Average, Worst case

Big O описує лише найгірший (worst case) сценарій. Але алгоритми мають ще два «обличчя»:

Для сортування бульбашкою:

• Best case (вже відсортований масив): O(n) — одна перевірка, без обмінів
• Average case: O(n²)
• Worst case (масив відсортований у зворотному порядку): O(n²)

Сортування бульбашкою (Bubble Sort)

Ідея алгоритму

Назва — від аналогії з бульбашками повітря у воді: що легша (менша) бульбашка — то швидше вона «спливає» вгору. В масиві «важкі» (великі) елементи «тонуть» вниз (до кінця), а «легкі» (малі) — «спливають» вгору (до початку).

Принцип: порівнюємо два сусідніх елементи. Якщо лівий більший за правий — міняємо їх місцями. Повторюємо для всіх пар. За один прохід (pass) найбільший елемент гарантовано опиняється на своєму місці — в кінці масиву. Потім повторюємо для решти (без останнього елемента, він вже на місці).

Покрокове трасування

Масив: {5, 3, 8, 1, 2}

Прохід 1 (порівнюємо пари, найбільший — на кінець):

8 зайняла своє місце ✅

Прохід 2 (без останнього):

5 на місці ✅

Прохід 3:

3 на місці ✅

Прохід 4:

Масив відсортований ✅ {1, 2, 3, 5, 8}

Реалізація

#include <iostream>

using namespace std;

int main()
{
    const int SIZE = 5;
    int arr[SIZE] = {5, 3, 8, 1, 2};

    // Зовнішній цикл: N-1 проходів
    for (int pass = 0; pass < SIZE - 1; pass++)
    {
        bool swapped = false;  // Прапор для оптимізації

        // Внутрішній цикл: -pass, бо хвіст вже відсортований
        for (int i = 0; i < SIZE - 1 - pass; i++)
        {
            if (arr[i] > arr[i + 1])
            {
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
                swapped = true;
            }
        }

        // Якщо жодного обміну — масив вже відсортований!
        if (!swapped)
        {
            break;
        }
    }

    for (int i = 0; i < SIZE; i++)
    {
        cout << arr[i] << " ";
    }
    cout << "\n";

    return 0;
}

Зверніть на оптимізацію з прапором swapped (рядки 13, 24, 28–31). Якщо за весь прохід жодного обміну не відбулося — масив вже відсортований, і ми виходимо достроково. Завдяки цьому best case стає O(n) замість O(n²): для вже відсортованого масиву потрібен лише один перевірочний прохід.

Аналіз складності

Коли використовувати: майже ніколи в продакшн-коді. Bubble sort — навчальний алгоритм. Єдиний реальний сценарій: перевірити, чи масив вже відсортований (з оптимізацією прапором).

Сортування вибіркою (Selection Sort)

Ідея алгоритму

Уявіть, що перед вами лежить купа іграшок різного розміру. Ви хочете розкласти їх від найменшої до найбільшої. Природний підхід: знаходите найменшу — кладете на перше місце. Потім знаходите найменшу з тих, що залишились — на друге місце. І так далі.

Принцип: ділимо масив на дві частини — «відсортовану» (ліворуч) та «невідсортовану» (праворуч). На кожному кроці знаходимо мінімальний елемент у невідсортованій частині та ставимо його на відповідне місце, міняючи з першим невідсортованим елементом.

Ключова відмінність від bubble sort: мінімум порядків обміну. В bubble sort обміни відбуваються часто. В selection sort — рівно N-1 обмін за весь алгоритм. Для ситуацій, де запис у пам'ять дорогий — це перевага.

Покрокове трасування

Масив: {5, 3, 8, 1, 2}

Крок 0: Шукаємо min у {5, 3, 8, 1, 2}
        min = 1 (індекс 3)
        Міняємо arr[0] і arr[3]:
        {1, 3, 8, 5, 2}
        ↑ відсортована частина

Крок 1: Шукаємо min у {3, 8, 5, 2}
        min = 2 (індекс 4)
        Міняємо arr[1] і arr[4]:
        {1, 2, 8, 5, 3}
        ↑↑ відсортована частина

Крок 2: Шукаємо min у {8, 5, 3}
        min = 3 (індекс 4)
        Міняємо arr[2] і arr[4]:
        {1, 2, 3, 5, 8}
        ↑↑↑ відсортована частина

Крок 3: Шукаємо min у {5, 8}
        min = 5 (індекс 3) — вже на місці, але все одно "обмінюємо"
        {1, 2, 3, 5, 8} ✅

Всього обмінів: 4 (рівно N-1). Для порівняння — bubble sort на тому самому масиві зробив би значно більше.

Реалізація

#include <iostream>

using namespace std;

int main()
{
    const int SIZE = 5;
    int arr[SIZE] = {5, 3, 8, 1, 2};

    for (int step = 0; step < SIZE - 1; step++)
    {
        // Знаходимо індекс мінімального елемента
        // у невідсортованій частині [step .. SIZE-1]
        int minIndex = step;

        for (int i = step + 1; i < SIZE; i++)
        {
            if (arr[i] < arr[minIndex])
            {
                minIndex = i;
            }
        }

        // Якщо мінімум — не вже поточний елемент, міняємо місцями
        if (minIndex != step)
        {
            int temp = arr[step];
            arr[step] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }

    for (int i = 0; i < SIZE; i++)
    {
        cout << arr[i] << " ";
    }
    cout << "\n";

    return 0;
}

Деталі реалізації:

• Рядок 14: minIndex = step — спочатку вважаємо, що мінімум — перший невідсортований елемент.
• Рядок 16: Внутрішній цикл починається з step + 1 — елементи до step вже на своїх місцях.
• Рядки 22–28: Перевірка if (minIndex != step) перед обміном — якщо мінімум вже на правильному місці, обмін не потрібен.

Аналіз складності

Важлива особливість: на відміну від bubble sort, selection sort не виграє від вже відсортованих даних — він все одно виконує всі порівняння. Але через мінімальну кількість обмінів він може бути швидшим за bubble sort на масивах, де операція письма у пам'ять повільніша за читання.

Сортування вставками (Insertion Sort)

Ідея алгоритму

Уявіть, як ви тримаєте карти в руці під час карткової гри. Отримавши нову карту, ви вставляєте її на правильне місце серед вже відсортованих карт: знаходите позицію, де нова карта «менша за наступну» та «більша за попередню» — і вставляєте туди.

Принцип: поділяємо масив на «вже відсортовану» ліву частину та «ще не опрацьовану» праву. Беремо перший невідсортований елемент — поточний (key). Зсуваємо всі елементи відсортованої частини, що більші за нього, на одну позицію вправо — «звільняємо місце». Вставляємо поточний елемент на правильну позицію.

Insertion sort особливо ефективний на майже відсортованих даних: якщо масив майже правильний, елементи вставляються практично без зсувів.

Покрокове трасування

Масив: {5, 3, 8, 1, 2}

Початок: [5] | {3, 8, 1, 2}
         ↑ відсортована частина (з одного елемента)

Крок 1: key = 3 (arr[1])
        Відсортована: {5}
        5 > 3 → зсуваємо 5 вправо: {_, 5, 8, 1, 2}
        Вставляємо key=3 на позицію 0: {3, 5} | {8, 1, 2}

Крок 2: key = 8 (arr[2])
        Відсортована: {3, 5}
        5 < 8 → зупиняємось одразу
        Вставляємо key=8 на позицію 2: {3, 5, 8} | {1, 2}

Крок 3: key = 1 (arr[3])
        Відсортована: {3, 5, 8}
        8 > 1 → зсуваємо 8: {3, 5, _, 8, 2}
        5 > 1 → зсуваємо 5: {3, _, 5, 8, 2}
        3 > 1 → зсуваємо 3: {_, 3, 5, 8, 2}
        Початок масиву → вставляємо key=1: {1, 3, 5, 8} | {2}

Крок 4: key = 2 (arr[4])
        Відсортована: {1, 3, 5, 8}
        8 > 2 → зсуваємо: {1, 3, 5, _, 8}
        5 > 2 → зсуваємо: {1, 3, _, 5, 8}
        3 > 2 → зсуваємо: {1, _, 3, 5, 8}
        1 < 2 → зупиняємось
        Вставляємо key=2 на позицію 1: {1, 2, 3, 5, 8} ✅

Реалізація

#include <iostream>

using namespace std;

int main()
{
    const int SIZE = 5;
    int arr[SIZE] = {5, 3, 8, 1, 2};

    for (int step = 1; step < SIZE; step++)
    {
        int key = arr[step];  // Поточний елемент для вставки
        int j = step - 1;     // Останній елемент відсортованої частини

        // Зсуваємо вправо елементи, що більші за key
        while (j >= 0 && arr[j] > key)
        {
            arr[j + 1] = arr[j];  // Зсуваємо на одну позицію вправо
            j--;
        }

        // j+1 — правильна позиція для key
        arr[j + 1] = key;
    }

    for (int i = 0; i < SIZE; i++)
    {
        cout << arr[i] << " ";
    }
    cout << "\n";

    return 0;
}

Ключові рядки:

• Рядок 10: Зовнішній цикл починається з 1 (не з 0): масив з одного елемента вже «відсортований».
• Рядок 12: key = arr[step] — зберігаємо копію поточного елемента, бо він буде перезаписаний при зсувах.
• Рядок 16: while (j >= 0 && arr[j] > key) — умови зупинки: або вийшли за початок масиву, або знайшли елемент менший за key.
• Рядок 18: arr[j + 1] = arr[j] — зсув без тимчасової змінної! Ми просто котимо елементи вправо, ніби котимо кулю по похилій поверхні.
• Рядок 22: arr[j + 1] = key — j після циклу вказує на перший елемент, що менший або рівний key. Тому key іде на позицію j+1.

Аналіз складності

Де insertion sort виграє: на малих масивах (до 15–30 елементів) та на майже відсортованих даних insertion sort часто швидший за quicksort — через менші константні накладні витрати. Тому багато реальних бібліотечних реалізацій quicksort перемикаються на insertion sort для малих підмасивів.

Швидке сортування (Quick Sort)

Ідея алгоритму: «розділяй і володарюй»

Quicksort — один з найефективніших алгоритмів сортування загального призначення та центральний приклад стратегії «розділяй і володарюй» (divide and conquer). Ідея: замість того, щоб вирішувати одну велику задачу, ми розбиваємо її на менші підзадачі аж до тривіального випадку.

Принцип:

1. Обираємо опорний елемент (pivot) — будь-який елемент масиву.
2. Розбиваємо (partition) масив на дві частини: ліворуч — всі елементи, що менші або рівні pivot, праворуч — всі, що більші.
3. Рекурсивно сортуємо ліву та праву частини.
4. Базовий випадок рекурсії: підмасив з 0 або 1 елемента вже «відсортований».

Операція partition: серце алгоритму

Partition — найважливіша та найхитріша частина quicksort. Розберемо варіант Lomuto partition scheme — простіший для розуміння:

Масив: {3, 6, 8, 10, 1, 2, 1}
Pivot: arr[right] = 1 (останній елемент)

i = -1  (« межа меншого» — inicially перед масивом)

j = 0: arr[0]=3. 3 > 1 → нічого
j = 1: arr[1]=6. 6 > 1 → нічого
j = 2: arr[2]=8. 8 > 1 → нічого
j = 3: arr[3]=10. 10 > 1 → нічого
j = 4: arr[4]=1. 1 <= 1 → i++, swap(arr[0], arr[4])
        {1, 6, 8, 10, 3, 2, 1}, i=0
j = 5: arr[5]=2. 2 > 1 → нічого
j = 6: (pivot, не входить у цикл)

Фінальний swap(arr[i+1], arr[right]): swap(arr[1], arr[6])
{1, 1, 8, 10, 3, 2, 6}
       ↑ pivot на своєму місці (індекс 1)

Після partition: всі елементи ліворуч від pivot ≤ pivot, праворуч — > pivot. Pivot на фінальній позиції.

Покрокове трасування quicksort

Масив: {5, 3, 8, 1, 2}, pivot = останній елемент

quickSort({5, 3, 8, 1, 2})
  pivot = 2
  partition: {1, 2, 8, 3, 5}
              ↑  ↑
         ліва  pivot  права
              |
  Ліва: {1} → вже відсортовано (1 елемент)
  Права: {8, 3, 5}
    quickSort({8, 3, 5})
      pivot = 5
      partition: {3, 5, 8}
                     ↑
                   pivot
      Ліва: {3} → відсортовано
      Права: {8} → відсортовано

Фінальний масив: {1, 2, 3, 5, 8} ✅

Реалізація

#include <iostream>

using namespace std;

// Допоміжна функція: міняє два елементи місцями
void swap(int& a, int& b)
{
    int temp = a;
    a = b;
    b = temp;
}

// Partition: розташовує pivot на правильній позиції,
// ліворуч — менші, праворуч — більші.
// Повертає індекс pivot.
int partition(int arr[], int low, int high)
{
    int pivot = arr[high];  // Обираємо останній елемент як pivot
    int i = low - 1;        // i — індекс останнього "малого" елемента

    for (int j = low; j < high; j++)
    {
        if (arr[j] <= pivot)
        {
            i++;
            swap(arr[i], arr[j]);
        }
    }

    // Ставимо pivot на своє місце
    swap(arr[i + 1], arr[high]);

    return i + 1;  // Повертаємо індекс pivot
}

// Рекурсивне сортування підмасиву arr[low..high]
void quickSort(int arr[], int low, int high)
{
    if (low < high)  // Базовий випадок: 0 або 1 елемент — вже відсортовано
    {
        int pivotIndex = partition(arr, low, high);

        // Рекурсивно сортуємо ліву та праву частини
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

int main()
{
    const int SIZE = 7;
    int arr[SIZE] = {10, 7, 8, 9, 1, 5, 3};

    quickSort(arr, 0, SIZE - 1);

    for (int i = 0; i < SIZE; i++)
    {
        cout << arr[i] << " ";
    }
    cout << "\n";

    return 0;
}

Розберемо архітектуру:

• swap (рядки 6–11): Допоміжна функція з параметрами-посиланнями (int& a). Посилання дозволяє змінити оригінальні значення, а не копії. Детально посилання розберемо у окремому розділі.
• partition (рядки 16–32): Схема Lomuto. Змінна i — межа «малих» елементів. Якщо елемент менший за pivot (arr[j] <= pivot), збільшуємо i та ставимо його у зону малих.
• quickSort (рядки 35–45): Рекурсивна функція. Умова if (low < high) — базовий випадок: підмасив із 0 або 1 елемента рекурсії не потребує.
• Рядок 51: quickSort(arr, 0, SIZE - 1) — запуск зі всім масивом.

Вибір pivot та його вплив

Вибір pivot може кардинально вплинути на ефективність:

{1, 2, 3, 4, 5}, pivot = 5
Розбивка: {} і {1, 2, 3, 4} — degenerujucha

Аналіз складності

Чому quicksort часто найшвидший на практиці (незважаючи на O(n²) у найгіршому випадку)?

1. Кеш-дружній: quicksort працює з підмасивами послідовно, що відповідає принципу локальності у кеші процесора.
2. Малі константи: порівняно з merge sort, quicksort не потребує додаткової пам'яті для злиття.
3. Рідкісний worst case: при рандомізованому pivot або медіані трьох — O(n²) вкрай малоймовірний.

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

Зведена таблиця

Коли що обирати?

Масштаб: як різниться час на практиці?

Для n = 10 000 елементів (орієнтовні значення):

Навіть 10 000 елементів вже показують суттєву різницю між O(n log n) та O(n²).

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

Рівень 1 — Базовий

Pass 1: 3 swaps
Pass 2: 2 swaps
Pass 3: 1 swaps
Pass 4: 1 swaps
Total swaps: 7

Рівень 2 — Логічний

// Фрагмент A
for (int i = 0; i < n; i++)
    for (int j = i; j < n; j++)
        sum += arr[i] + arr[j];

// Фрагмент B
int x = arr[n / 2];

// Фрагмент C
for (int i = 1; i < n; i *= 2)
    cout << i;

// Фрагмент D
for (int i = 0; i < n; i++)
    for (int j = 0; j < 10; j++)
        arr[i] += j;

Рівень 3 — Творчий

Input:
Alice 850
Bob 1200
Carol 650
Dave 1100
Eve 900

Output:
1. Bob    - 1200
2. Dave   - 1100
3. Eve    - 900
4. Alice  - 850
5. Carol  - 650

Підсумок