Перейти до змісту

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

Вступ: що таке сортування і навіщо воно потрібне

Сортування — це впорядкування елементів за певним критерієм: за зростанням, за спаданням, за ключем у структурі даних.

Де зустрічається сортування

  • Упорядкування оцінок студентів за рейтингом
  • Сортування файлів за датою
  • Підготовка даних для бінарного пошуку (пошук у відсортованому масиві працює за \(O(\log n)\), а не за \(O(n)\))
  • Виведення результатів у зручному для читання порядку

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

Ключові терміни

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

Термін Значення
in-place Алгоритм працює з мінімальною додатковою пам'яттю — сортує "на місці"
stable sort Елементи з однаковими ключами зберігають свій відносний порядок
Часова складність Скільки операцій виконує алгоритм залежно від кількості елементів \(n\)
Просторова складність Скільки додаткової пам'яті потрібно алгоритму

Класифікація алгоритмів цієї лекції

flowchart TB
    S["Алгоритми сортування"]
    S --> Simple["Прості — O(n²)"]
    S --> Efficient["Ефективні — O(n log n)"]
    Simple --> BS["Bubble Sort\n(бульбашкове)"]
    Simple --> IS["Insertion Sort\n(вставками)"]
    Efficient --> QS["Quicksort\n(швидке)"]
    Efficient --> MS["Merge Sort\n(злиттям)"]

Наш vector: додаємо get_size()

У попередніх лекціях ми створили шаблонний vector<T>. Нагадаємо його ключові частини:

template<typename T>
struct vector {
    T* data;
    int size;
    int capacity;

    vector(int initial_capacity = 4) {
        data = new T[initial_capacity];
        size = 0;
        capacity = initial_capacity;
    }

    vector(std::initializer_list<T> init) {
        capacity = init.size() * 2;
        if (capacity < 4) capacity = 4;
        size = init.size();
        data = new T[capacity];

        const T* ptr = init.begin();
        for (int j = 0; j < (int)init.size(); ++j) {
            data[j] = ptr[j];
        }
    }

    ~vector() {
        delete[] data;
    }

    // ... resize, push_back, at, operator[] ...
};

Зараз поле size — публічне. Це означає, що будь-хто може написати v.size = -100 і зламати вектор. В об'єктно-орієнтованому програмуванні існує принцип інкапсуляції — приховування внутрішнього стану об'єкта, щоб зовнішній код міг взаємодіяти з ним тільки через контрольовані методи.

Додамо метод get_size(), який повертає розмір безпечно:

template<typename T>
struct vector {
    // ... all previous members ...

    int get_size() {
        return size;
    }
};

Навіщо get_size()?

Поки що ми не будемо ховати поле size (для цього потрібно познайомитися з private/public). Але метод get_size() — перший крок до інкапсуляції: зовнішній код не змінює size напряму, а лише читає його через метод.

В алгоритмах сортування нижче ми будемо використовувати як v.get_size(), так і прямий доступ до v.data — адже алгоритми працюють із масивом всередині вектора.

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

Ідея

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

Покроковий приклад

Для масиву [5, 3, 8, 4, 2]:

Прохід 1 — шукаємо найбільший елемент:

flowchart LR
    subgraph "Прохід 1"
        direction TB
        s1["[5, 3, 8, 4, 2] — 5 > 3? Так, обмін"]
        s2["[3, 5, 8, 4, 2] — 5 > 8? Ні"]
        s3["[3, 5, 8, 4, 2] — 8 > 4? Так, обмін"]
        s4["[3, 5, 4, 8, 2] — 8 > 2? Так, обмін"]
        s5["[3, 5, 4, 2, 8] — 8 на місці ✓"]
        s1 --> s2 --> s3 --> s4 --> s5
    end

Після першого проходу 8 вже стоїть на своєму місці. Тепер внутрішній цикл може не перевіряти останній елемент.

Прохід 2: [3, 5, 4, 2, 8] → [3, 4, 2, 5, 8]

Прохід 3: [3, 4, 2, 5, 8] → [3, 2, 4, 5, 8]

Прохід 4: [3, 2, 4, 5, 8] → [2, 3, 4, 5, 8] — готово!

Реалізація

template<typename T>
void bubble_sort(vector<T>& v) {
    int n = v.get_size();
    for (int i = 0; i < n - 1; ++i) {
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; ++j) {
            if (v[j] > v[j + 1]) {
                std::swap(v[j], v[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) {
            break; // Array is already sorted
        }
    }
}

Оптимізація через swapped

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

Що відбувається в коді

  • Зовнішній цикл (i) — кількість проходів. Після i-го проходу останні i елементів вже на своїх місцях.
  • Внутрішній цикл (j) — порівняння сусідніх елементів. Межа n - 1 - i, бо останні i елементів вже відсортовані.
  • std::swap — стандартна функція для обміну двох значень.

Повний приклад

#include <iostream>
#include <cassert>
#include <initializer_list>

template<typename T>
struct vector {
    T* data;
    int size;
    int capacity;

    vector(std::initializer_list<T> init) {
        capacity = init.size() * 2;
        if (capacity < 4) capacity = 4;
        size = init.size();
        data = new T[capacity];
        const T* ptr = init.begin();
        for (int j = 0; j < (int)init.size(); ++j) {
            data[j] = ptr[j];
        }
    }

    ~vector() { delete[] data; }

    int get_size() { return size; }

    T& operator[](int index) {
        assert(index >= 0 && index < size);
        return data[index];
    }
};

template<typename T>
void bubble_sort(vector<T>& v) {
    int n = v.get_size();
    for (int i = 0; i < n - 1; ++i) {
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; ++j) {
            if (v[j] > v[j + 1]) {
                std::swap(v[j], v[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

int main() {
    vector<int> v = {5, 3, 8, 4, 2};

    bubble_sort(v);

    for (int i = 0; i < v.get_size(); ++i) {
        std::cout << v[i] << " ";
    }
    std::cout << std::endl; // 2 3 4 5 8

    return 0;
}

Складність

Випадок Складність
Найкращий (вже відсортований) \(O(n)\)
Середній \(O(n^2)\)
Найгірший (зворотній порядок) \(O(n^2)\)
Додаткова пам'ять \(O(1)\) — in-place

Стабільність: так — однакові елементи не міняються місцями.

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

Ідея

Аналогія з картами

Уявіть, що ви тримаєте карти в руці. Кожну нову карту ви вставляєте на правильне місце серед вже відсортованих. Саме так працює insertion sort.

Масив умовно ділиться на дві частини:

  • ліва — вже відсортована
  • права — ще не оброблена

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

Покроковий приклад

Для масиву [5, 3, 8, 4, 2]:

Крок Дія Результат
1 Беремо 3, вставляємо перед 5 [3, 5, 8, 4, 2]
2 Беремо 8 — вже на місці [3, 5, 8, 4, 2]
3 Беремо 4, вставляємо між 3 і 5 [3, 4, 5, 8, 2]
4 Беремо 2, вставляємо на початок [2, 3, 4, 5, 8] 
flowchart LR
    subgraph "Крок 3: вставляємо 4"
        direction TB
        a1["[3, 5, 8, |4|, 2] — key = 4"]
        a2["8 > 4 → зсув: [3, 5, _, 8, 2]"]
        a3["5 > 4 → зсув: [3, _, 5, 8, 2]"]
        a4["3 < 4 → стоп, вставляємо: [3, 4, 5, 8, 2]"]
        a1 --> a2 --> a3 --> a4
    end

Реалізація

template<typename T>
void insertion_sort(vector<T>& v) {
    int n = v.get_size();
    for (int i = 1; i < n; ++i) {
        T key = v[i];
        int j = i - 1;
        while (j >= 0 && v[j] > key) {
            v[j + 1] = v[j]; // Shift element to the right
            --j;
        }
        v[j + 1] = key; // Insert key at the correct position
    }
}

Що відбувається в коді

  • key — елемент, який потрібно вставити на правильне місце.
  • Цикл while — рухаємося вліво по відсортованій частині. Поки елементи більші за key, зсуваємо їх вправо на одну позицію.
  • v[j + 1] = key — коли знайшли правильне місце, вставляємо key.

Порівняння з Bubble Sort

Bubble Sort Insertion Sort
Стратегія Обмін сусідніх Вставка на правильне місце
Майже відсортований масив Швидкий (\(O(n)\)) Швидкий (\(O(n)\))
Практична швидкість Повільніший Швидший (менше обмінів)
Кількість обмінів Багато Мало (зсуви замість обмінів)

Чому insertion sort кращий на практиці

Insertion sort робить зсуви (одне присвоєння), а bubble sort — обміни (три присвоєння через swap). На майже відсортованих даних insertion sort виконує мінімум роботи, бо цикл while завершується одразу.

Складність

Випадок Складність
Найкращий (вже відсортований) \(O(n)\)
Середній \(O(n^2)\)
Найгірший (зворотній порядок) \(O(n^2)\)
Додаткова пам'ять \(O(1)\) — in-place

Стабільність: так — ми зсуваємо тільки елементи, що строго більші за key.

Quicksort (швидке сортування)

Ідея: розділяй і владарюй

Quicksort базується на стратегії divide and conquer (розділяй і владарюй). Ця стратегія полягає в тому, щоб розбити складну задачу на кілька простіших підзадач, розв'язати кожну окремо, а потім об'єднати результати. У випадку quicksort:

  1. Divide (розділяй): вибрати опорний елемент (pivot) і розбити масив на дві частини — елементи менші за pivot і більші або рівні pivot
  2. Conquer (владарюй): рекурсивно відсортувати кожну частину
  3. Combine (об'єднуй): нічого робити не потрібно — після розбиття і сортування частин масив уже відсортований
flowchart TB
    A["[5, 3, 8, 4, 2]\npivot = 2"] --> B["partition"]
    B --> L["[  ] — менші за 2"]
    B --> P["[2]"]
    B --> R["[5, 3, 8, 4] — більші за 2"]
    L --> LS["[  ]"]
    R --> R2["pivot = 4"]
    R2 --> RL["[3] — менші за 4"]
    R2 --> RP["[4]"]
    R2 --> RR["[5, 8] — більші за 4"]
    RL --> RLS["[3]"]
    RR --> RR2["pivot = 8"]
    RR2 --> RRL["[5]"]
    RR2 --> RRP["[8]"]
    RRP --> Result["Результат: [2, 3, 4, 5, 8]"]
    RRL --> Result
    RLS --> Result
    RP --> Result
    LS --> Result
    P --> Result

Partition: серце алгоритму

Функція partition переставляє елементи так, щоб pivot опинився на своїй фінальній позиції: всі елементи зліва менші за нього, всі справа — більші або рівні.

Існує кілька варіантів реалізації partition. Ми використаємо схему Ломуто (Lomuto partition scheme), названу на честь програміста Ніко Ломуто (Nico Lomuto). Вона стала широко відомою завдяки книзі Джона Бентлі "Programming Pearls" як простіша альтернатива до оригінальної схеми Хоара (Hoare partition scheme) — автора самого алгоритму quicksort (Тоні Хоар, 1960 рік). Ідея схеми Ломуто: обираємо останній елемент як pivot і проходимо масив зліва направо, підтримуючи індекс i — межу між елементами, що менші за pivot, і рештою.

Розглянемо роботу на прикладі [5, 3, 8, 4, 2], де pivot — останній елемент (2):

Крок j a[j] < pivot? Дія Стан масиву i
0 0 5 < 2? Ні — [5, 3, 8, 4, 2] -1
1 1 3 < 2? Ні — [5, 3, 8, 4, 2] -1
2 2 8 < 2? Ні — [5, 3, 8, 4, 2] -1
3 3 4 < 2? Ні — [5, 3, 8, 4, 2] -1
Фінал swap(a[0], a[4]) [2, 3, 8, 4, 5] 0

Pivot 2 тепер на позиції 0 — це його фінальне місце.

Реалізація

template<typename T>
int partition(vector<T>& v, int low, int high) {
    T pivot = v[high]; // Choose the last element as pivot
    int i = low - 1;   // Index of the boundary between "less" and "greater"

    for (int j = low; j < high; ++j) {
        if (v[j] < pivot) {
            ++i;
            std::swap(v[i], v[j]);
        }
    }
    std::swap(v[i + 1], v[high]); // Place pivot at its final position
    return i + 1;                  // Return pivot's position
}

template<typename T>
void quick_sort_recursive(vector<T>& v, int low, int high) {
    if (low < high) {
        int pi = partition(v, low, high);
        quick_sort_recursive(v, low, pi - 1);  // Sort left part
        quick_sort_recursive(v, pi + 1, high);  // Sort right part
    }
}

template<typename T>
void quick_sort(vector<T>& v) {
    quick_sort_recursive(v, 0, v.get_size() - 1);
}

Що відбувається в коді

  • partition() — проходить масив зліва направо. Індекс i відстежує межу між елементами, меншими за pivot, і рештою. Коли зустрічаємо елемент менший за pivot, збільшуємо i і переміщуємо цей елемент у "ліву" зону.
  • quick_sort_recursive() — рекурсивно сортує ліву і праву частини. Після partition pivot уже на своєму місці — його не потрібно рухати.
  • quick_sort() — зручна обгортка, яка приховує деталі рекурсії.

Найгірший випадок Quicksort

Якщо pivot завжди виявляється найменшим або найбільшим елементом (наприклад, масив уже відсортований, а ми завжди берем останній елемент), розбиття буде нерівномірним: одна частина порожня, інша — n-1 елементів. Це призводить до \(O(n^2)\) операцій.

На практиці цю проблему вирішують вибором медіани або випадкового pivot, але це виходить за межі цієї лекції.

Складність

Випадок Складність
Найкращий (рівномірне розбиття) \(O(n \log n)\)
Середній \(O(n \log n)\)
Найгірший (нерівномірне розбиття) \(O(n^2)\)
Додаткова пам'ять (стек рекурсії) \(O(\log n)\) в середньому

Стабільність: ні — swap у partition може змінити порядок однакових елементів.

Merge Sort (сортування злиттям)

Ідея

Merge sort — ще один алгоритм на основі divide and conquer, але з гарантованою складністю \(O(n \log n)\). На відміну від quicksort, тут основна робота відбувається на етапі combine:

  1. Divide: поділити масив на дві половини (просто навпіл, без порівнянь)
  2. Conquer: рекурсивно відсортувати кожну половину
  3. Combine: злити дві відсортовані половини в один відсортований масив — саме тут відбувається вся робота
flowchart TB
    A["[5, 3, 8, 4, 2]"] --> B["[5, 3]"]
    A --> C["[8, 4, 2]"]
    B --> D["[5]"]
    B --> E["[3]"]
    C --> F["[8]"]
    C --> G["[4, 2]"]
    G --> H["[4]"]
    G --> I["[2]"]
    D --> J["merge → [3, 5]"]
    E --> J
    H --> K["merge → [2, 4]"]
    I --> K
    F --> L["merge → [2, 4, 8]"]
    K --> L
    J --> M["merge → [2, 3, 4, 5, 8]"]
    L --> M

Злиття: серце алгоритму

Операція злиття (merge) — найважливіша частина. Маємо два відсортовані підмасиви та повинні об'єднати їх в один відсортований масив.

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

Крок Лівий Правий Порівняння Результат
1 3, 5 2, 4, 8 3 > 2 [2]
2 3, 5 4, 8 3 < 4 [2, 3]
3 5 4, 8 5 > 4 [2, 3, 4]
4 5 8 5 < 8 [2, 3, 4, 5]
5 — 8 залишок [2, 3, 4, 5, 8]

Реалізація

template<typename T>
void merge(vector<T>& v, int left, int mid, int right) {
    int n = right - left + 1;
    T* temp = new T[n]; // Temporary buffer for merged result
    int i = left;       // Pointer for left half
    int j = mid + 1;    // Pointer for right half
    int k = 0;          // Pointer for temp array

    // Merge two halves by comparing elements
    while (i <= mid && j <= right) {
        if (v[i] <= v[j]) {
            temp[k] = v[i];
            ++i;
        } else {
            temp[k] = v[j];
            ++j;
        }
        ++k;
    }

    // Copy remaining elements from left half
    while (i <= mid) {
        temp[k] = v[i];
        ++i;
        ++k;
    }

    // Copy remaining elements from right half
    while (j <= right) {
        temp[k] = v[j];
        ++j;
        ++k;
    }

    // Copy merged result back to original vector
    for (int m = 0; m < n; ++m) {
        v[left + m] = temp[m];
    }

    delete[] temp; // Free temporary memory
}

template<typename T>
void merge_sort_recursive(vector<T>& v, int left, int right) {
    if (left >= right) {
        return; // Base case: 0 or 1 elements
    }
    int mid = left + (right - left) / 2;
    merge_sort_recursive(v, left, mid);       // Sort left half
    merge_sort_recursive(v, mid + 1, right);  // Sort right half
    merge(v, left, mid, right);               // Merge sorted halves
}

template<typename T>
void merge_sort(vector<T>& v) {
    merge_sort_recursive(v, 0, v.get_size() - 1);
}

Що відбувається в коді

  • merge() — створює тимчасовий масив temp через new T[], зливає в нього два відсортовані підмасиви, потім копіює результат назад. В кінці — delete[] temp для звільнення пам'яті.
  • merge_sort_recursive() — ділить масив навпіл, рекурсивно сортує обидві половини, потім зливає.
  • merge_sort() — обгортка, аналогічна quick_sort().

Чому new T[] а не vector?

Ми свідомо використовуємо сирий масив new T[] для тимчасового буфера. Це демонструє роботу з динамічною пам'яттю вручну, що є важливим навиком. В реальному коді для цього використовують std::vector.

Складність

Випадок Складність
Найкращий \(O(n \log n)\)
Середній \(O(n \log n)\)
Найгірший \(O(n \log n)\)
Додаткова пам'ять \(O(n)\)

Стабільність: так — при рівних елементах ми беремо спочатку з лівого підмасиву (v[i] <= v[j]), зберігаючи початковий порядок.

Гарантована складність

На відміну від quicksort, merge sort завжди працює за \(O(n \log n)\), незалежно від вхідних даних. Це його головна перевага. Ціна — додаткова пам'ять \(O(n)\) для тимчасового масиву.

Сортування кастомних типів

Усі алгоритми вище працюють з будь-яким типом, для якого визначено оператор > (або <). Але що робити, якщо ми хочемо сортувати за іншим критерієм?

Наприклад, сортувати точки за x-координатою, або студентів за оцінкою.

Рішення: компаратор

Компаратор — це функція, яка приймає два елементи і повертає true, якщо перший повинен стояти перед другим.

Додамо параметр-компаратор до bubble sort (аналогічно можна зробити з будь-яким іншим алгоритмом):

template<typename T, typename Compare>
void bubble_sort(vector<T>& v, Compare comp) {
    int n = v.get_size();
    for (int i = 0; i < n - 1; ++i) {
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; ++j) {
            if (comp(v[j + 1], v[j])) { // Use comparator instead of >
                std::swap(v[j], v[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

Приклад: сортування точок

Використаємо структуру point з попередньої лекції та відсортуємо точки за x-координатою:

#include <iostream>
#include <cassert>
#include <initializer_list>

template<typename T>
struct vector {
    T* data;
    int size;
    int capacity;

    vector(std::initializer_list<T> init) {
        capacity = init.size() * 2;
        if (capacity < 4) capacity = 4;
        size = init.size();
        data = new T[capacity];
        const T* ptr = init.begin();
        for (int j = 0; j < (int)init.size(); ++j) {
            data[j] = ptr[j];
        }
    }
    ~vector() { delete[] data; }
    int get_size() { return size; }
    T& operator[](int index) {
        assert(index >= 0 && index < size);
        return data[index];
    }
};

struct point {
    int x;
    int y;
};

std::ostream& operator<<(std::ostream& out, const point& p) {
    out << "(" << p.x << ", " << p.y << ")";
    return out;
}

// Comparator: sort by x-coordinate
bool compare_by_x(const point& a, const point& b) {
    return a.x < b.x;
}

// Comparator: sort by y-coordinate
bool compare_by_y(const point& a, const point& b) {
    return a.y < b.y;
}

template<typename T, typename Compare>
void bubble_sort(vector<T>& v, Compare comp) {
    int n = v.get_size();
    for (int i = 0; i < n - 1; ++i) {
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; ++j) {
            if (comp(v[j + 1], v[j])) {
                std::swap(v[j], v[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

int main() {
    vector<point> points = {
        {10, 3},
        {2, 15},
        {7, 1},
        {5, 8}
    };

    bubble_sort(points, compare_by_x);

    std::cout << "Sorted by x:" << std::endl;
    for (int i = 0; i < points.get_size(); ++i) {
        std::cout << "  " << points[i] << std::endl;
    }

    return 0;
}

Вивід: 

Sorted by x:
  (2, 15)
  (5, 8)
  (7, 1)
  (10, 3)

Один алгоритм — різні критерії

Змінивши лише функцію-компаратор, ми можемо сортувати ті самі дані за будь-яким полем: за x, за y, за відстанню від початку координат тощо. Це демонструє силу шаблонів і узагальненого програмування.

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

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

Алгоритм Найкращий Середній Найгірший Пам'ять Стабільність In-place
Bubble Sort \(O(n)\) \(O(n^2)\) \(O(n^2)\) \(O(1)\) Так Так
Insertion Sort \(O(n)\) \(O(n^2)\) \(O(n^2)\) \(O(1)\) Так Так
Quicksort \(O(n \log n)\) \(O(n \log n)\) \(O(n^2)\) \(O(\log n)\) Ні Так
Merge Sort \(O(n \log n)\) \(O(n \log n)\) \(O(n \log n)\) \(O(n)\) Так Ні

Наочний приклад: чому складність має значення

Порівняємо кількість операцій для різних розмірів масиву:

\(n\) \(n^2\) \(n \log_2 n\) Різниця
10 100 ~33 3×
100 10 000 ~664 15×
1 000 1 000 000 ~9 966 100×
10 000 100 000 000 ~132 877 753×

Масштабування

При \(n = 10\,000\) алгоритм \(O(n^2)\) виконає 100 мільйонів операцій, а \(O(n \log n)\) — лише ~133 тисячі. Це різниця між мілісекундами і секундами роботи програми.

Коли який алгоритм використовувати

flowchart TB
    Q["Який алгоритм обрати?"]
    Q --> S{"Масив малий?\n(< 50 елементів)"}
    S -->|Так| IS["Insertion Sort\n— простий і швидкий\nна малих даних"]
    S -->|Ні| G{"Потрібна гарантована\nшвидкість?"}
    G -->|Так| MS["Merge Sort\n— завжди O(n log n)\n— стабільний"]
    G -->|Ні| QS["Quicksort\n— найшвидший на практиці\n— in-place"]

Big-O: короткий довідник

Складність Назва Приклад
\(O(1)\) Константна Доступ до елемента за індексом
\(O(\log n)\) Логарифмічна Бінарний пошук
\(O(n)\) Лінійна Один прохід по масиву
\(O(n \log n)\) Лінеарифмічна Ефективне сортування
\(O(n^2)\) Квадратична Прості алгоритми сортування

Підсумок

Концепція Що запам'ятати
Bubble Sort Найпростіший, порівнює сусідні елементи, \(O(n^2)\)
Insertion Sort Вставляє елемент на правильне місце, ефективний на малих/майже відсортованих даних
Quicksort Divide and conquer, найшвидший на практиці, але \(O(n^2)\) у найгіршому випадку
Merge Sort Divide and conquer, гарантовано \(O(n \log n)\), потребує \(O(n)\) додаткової пам'яті
Компаратор Дозволяє сортувати за будь-яким критерієм без зміни алгоритму

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

  1. Як працює алгоритм? — описати принцип словами
  2. Яка його складність? — назвати часову і просторову складність
  3. Коли його доречно використовувати? — знати переваги і недоліки

Попередня: Оцінка складності | Задачі: Сортування