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

Задачі: Алгоритми сортування

Практичні задачі на тему алгоритмів сортування з використанням шаблонного vector<T>.

Формат задач

У кожній задачі дано сигнатуру функції. Потрібно написати реалізацію замість .... Всі функції — вільні шаблонні функції, що працюють з vector<T> з лекції.

Bubble Sort

Задача 1: Сортування за спаданням

Модифікуйте bubble sort так, щоб він сортував за спаданням (від більшого до меншого).

template<typename T>
void bubble_sort_desc(vector<T>& v) {
    ...
}

Приклад: [5, 3, 8, 4, 2] → [8, 5, 4, 3, 2]

Задача 2: Підрахунок обмінів

Напишіть варіант bubble sort, який повертає кількість виконаних обмінів.

template<typename T>
int bubble_sort_count(vector<T>& v) {
    ...
}

Приклад: [5, 3, 8, 4, 2] → повертає кількість swap-ів

Задача 3: Сортування частини масиву

Напишіть bubble sort, який сортує лише елементи від індексу left до right включно.

template<typename T>
void bubble_sort_range(vector<T>& v, int left, int right) {
    ...
}

Приклад: [9, 5, 3, 8, 4, 2, 7], left=2, right=5 → [9, 5, 2, 3, 4, 8, 7]

Задача 4: Перевірка відсортованості

Напишіть функцію, що перевіряє, чи вектор відсортований за зростанням.

template<typename T>
bool is_sorted(vector<T>& v) {
    ...
}

Приклад: [1, 2, 3, 5] → true, [1, 3, 2] → false

Insertion Sort

Задача 5: Вставка в відсортований вектор

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

template<typename T>
void insert_sorted(vector<T>& v, T value) {
    ...
}

Приклад: [2, 4, 6, 8], value=5 → [2, 4, 5, 6, 8]

Задача 6: Insertion sort за спаданням

Модифікуйте insertion sort для сортування за спаданням.

template<typename T>
void insertion_sort_desc(vector<T>& v) {
    ...
}

Задача 7: Кількість зсувів

Напишіть варіант insertion sort, який повертає загальну кількість зсувів (присвоєнь v[j+1] = v[j]).

template<typename T>
int insertion_sort_count(vector<T>& v) {
    ...
}

Підказка: кількість зсувів дорівнює кількості інверсій у масиві (пар елементів, що стоять у неправильному порядку).

Задача 8: Binary insertion sort

В insertion sort пошук місця для вставки можна прискорити за допомогою бінарного пошуку. Реалізуйте цей варіант.

template<typename T>
void binary_insertion_sort(vector<T>& v) {
    ...
}

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

Quicksort

Задача 9: Partition з іншим pivot

Модифікуйте partition так, щоб pivot був першим елементом, а не останнім.

template<typename T>
int partition_first(vector<T>& v, int low, int high) {
    ...
}

Задача 10: Підрахунок рекурсивних викликів

Напишіть quicksort, який підраховує та повертає загальну кількість рекурсивних викликів.

template<typename T>
int quick_sort_count(vector<T>& v) {
    ...
}

Підказка: передавайте лічильник за посиланням у рекурсивну функцію.

Задача 11: Пошук k-го елемента (quickselect)

Використовуючи ідею partition з quicksort, знайдіть k-й за величиною елемент без повного сортування масиву.

template<typename T>
T quick_select(vector<T>& v, int k) {
    ...
}

Приклад: [5, 3, 8, 4, 2], k=2 → 3 (другий за величиною)

Підказка: після partition pivot стоїть на позиції pi. Якщо pi == k, відповідь знайдена. Якщо k < pi, шукаємо зліва. Якщо k > pi, шукаємо справа.

Задача 12: Three-way partition

Модифікуйте partition для випадку, коли масив містить багато однакових елементів. Після partition масив має три зони: менші за pivot, рівні pivot, більші за pivot.

template<typename T>
void partition_3way(vector<T>& v, int low, int high, int& lt, int& gt) {
    // After call: v[low..lt-1] < pivot, v[lt..gt] == pivot, v[gt+1..high] > pivot
    ...
}

Merge Sort

Задача 13: Злиття двох відсортованих векторів

Дано два відсортовані вектори. Створіть новий вектор, що містить всі елементи обох у відсортованому порядку.

template<typename T>
vector<T> merge_vectors(vector<T>& a, vector<T>& b) {
    ...
}

Приклад: [1, 3, 5] і [2, 4, 6] → [1, 2, 3, 4, 5, 6]

Задача 14: Підрахунок інверсій через merge sort

Інверсія — це пара індексів \((i, j)\), де \(i < j\), але \(a[i] > a[j]\). Модифікуйте merge sort, щоб підрахувати кількість інверсій у масиві.

template<typename T>
int count_inversions(vector<T>& v) {
    ...
}

Приклад: [5, 3, 8, 4, 2] → 7 інверсій

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

Задача 15: Bottom-up merge sort

Реалізуйте merge sort без рекурсії (ітеративний варіант). Починаємо з блоків розміру 1 і поступово зливаємо сусідні блоки.

template<typename T>
void merge_sort_iterative(vector<T>& v) {
    ...
}

Підказка: зовнішній цикл збільшує розмір блоку (1, 2, 4, 8, ...). Внутрішній цикл зливає сусідні пари блоків.

Задача 16: Natural merge sort

Модифікуйте merge sort так, щоб він спочатку знаходив вже відсортовані ділянки (runs) у масиві, а потім зливав їх.

template<typename T>
void natural_merge_sort(vector<T>& v) {
    ...
}

Приклад: [1, 3, 5, 2, 4, 6] має два runs: [1, 3, 5] і [2, 4, 6] — достатньо одного злиття.

Порівняння та аналіз

Задача 17: Емпіричне порівняння

Напишіть програму, яка:

  1. Генерує випадковий вектор з n елементів
  2. Сортує його кожним з 4 алгоритмів (окремі копії!)
  3. Вимірює час кожного алгоритму

Порівняйте результати для n = 100, n = 1000, n = 10000.

Підказка: для вимірювання часу використовуйте <chrono>: 

#include <chrono>

auto start = std::chrono::high_resolution_clock::now();
// ... sorting ...
auto end = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
std::cout << "Time: " << duration.count() << " us" << std::endl;

Задача 18: Найгірший випадок quicksort

Створіть масив, на якому quicksort (з pivot = останній елемент) працює за \(O(n^2)\). Поясніть, чому це відбувається.

// Construct the worst-case array and sort it
int main() {
    ...
}

Кастомні компаратори

Задача 19: Сортування студентів

Дано структуру student. Відсортуйте вектор студентів:

  • a) за оцінкою (grade) за спаданням
  • b) за віком (age) за зростанням
struct student {
    int id;
    int age;
    double grade;
};

bool compare_by_grade_desc(const student& a, const student& b) {
    ...
}

bool compare_by_age(const student& a, const student& b) {
    ...
}

Задача 20: Сортування точок за відстанню

Відсортуйте вектор точок за відстанню від початку координат \((0, 0)\).

struct point {
    int x;
    int y;
};

bool compare_by_distance(const point& a, const point& b) {
    ...
}

Підказка: відстань від \((0,0)\) — це \(\sqrt{x^2 + y^2}\). Але для порівняння достатньо порівнювати \(x^2 + y^2\) без кореня (корінь — монотонна функція).

Лекція: Алгоритми сортування