Упражнения - Алгоритми за Сортиране

Напредък

✅ Завършени: 0 / 0📊 Напредък: 0%

💡 Напредъкът се записва локално в браузъра

ЛЕСНИ ЗАДАЧИ (Основни Концепции)

Упражнение

5 minЛЕСНО

Задача 1: Основна Терминология

Кое от следните твърдения за сортиране е ВЯРНО?

A) Стабилен сорт винаги работи по-бързо от нестабилен сорт
B) Стабилен сорт запазва относителната подредба на равни елементи
C) In-place сорт винаги използва O(n) допълнителна памет
D) Всички алгоритми за сортиране имат O(n²) worst-case сложност

Правилен отговор: B

B) Стабилен сорт запазва относителната подредба на равни елементи ✅ ВЯРНО
A) Стабилността не определя скоростта
C) In-place използва O(1) допълнителна памет, не O(n)
D) Има алгоритми с O(n log n) worst-case (merge sort, heap sort)

Упражнение

5 minЛЕСНО

Задача 2: Big-O Разпознаване

Каква е времевата сложност на следния код?

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        arr[i] += arr[j];
    }
}

A) O(n)
B) O(n²)
C) O(n log n)
D) O(2n)

Правилен отговор: B) O(n²)

Имаме два вложени цикъла, всеки от които върти n пъти:

Външният цикъл: n итерации
Вътрешният цикъл: n итерации
Общо: n × n = n² операции

Упражнение

10 minЛЕСНО

Задача 3: Swap Операция

Завършете следния код за размяна на два елемента в масив:

void swapElements(int arr[], int i, int j) {
    // Напишете вашия код тук
}

Има няколко начина:

Използвайте std::swap()
Използвайте временна променлива
Използвайте XOR trick (не препоръчително за четливост)

Решение 1: С std::swap (препоръчително)

void swapElements(int arr[], int i, int j) {
    std::swap(arr[i], arr[j]);
}

Решение 2: С временна променлива

void swapElements(int arr[], int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

Решение 3: XOR trick (не препоръчително)

void swapElements(int arr[], int i, int j) {
    if (i != j) {  // Важно! Не работи ако i == j
        arr[i] ^= arr[j];
        arr[j] ^= arr[i];
        arr[i] ^= arr[j];
    }
}

Упражнение

5 minЛЕСНО

Задача 4: Идентификация на Алгоритъм

Кой алгоритъм за сортиране се описва така: "Намира минималния елемент от несортираната част и го поставя в началото"?

A) Bubble Sort
B) Selection Sort
C) Insertion Sort
D) Merge Sort

Правилен отговор: B) Selection Sort

Selection sort работи като:

Намира минимума в несортираната част
Размяна с първия елемент на несортираната част
Повтаря за останалите елементи

Упражнение

5 minЛЕСНО

Задача 5: Предимство на Binary Search

Ако имате 1,000,000 сортирани елемента, приблизително колко сравнения изисква binary search в най-лошия случай?

A) 10
B) 20
C) 100
D) 500,000

Binary search има сложност O(log₂ n). Използвайте формулата:

log₂(1,000,000) ≈ ?

Правилен отговор: B) 20

Binary search сложност: O(log₂ n)

log₂(1,000,000) ≈ log₂(2²⁰) = 20

Всяко сравнение разполовява търсеното пространство:

1,000,000 → 500,000 → 250,000 → ... → 1

Упражнение

15 minЛЕСНО

Задача 6: Bubble Sort Trace

Проследете ЕДИН проход на bubble sort на масива [5, 2, 8, 1]. Покажете състоянието на масива след всяко сравнение/размяна.

Начално състояние: [5, 2, 8, 1]

Проход 1:

Стъпка	Сравнение	Размяна?	Масив след стъпката
1	5 vs 2	Да	`[2, 5, 8, 1]`
2	5 vs 8	Не	`[2, 5, 8, 1]`
3	8 vs 1	Да	`[2, 5, 1, 8]`

Резултат след първи проход: [2, 5, 1, 8]

Най-големият елемент (8) е "изплувал" към края на масива.

Упражнение

10 minЛЕСНО

Задача 7: Свойства на Алгоритмите

Съпоставете всяко свойство с правилния алгоритъм:

Алгоритми:

Insertion Sort
Selection Sort
Bubble Sort

Свойства:

A) Не е стабилен
B) Адаптивен (бърз на почти сортирани данни)
C) Винаги прави един и същ брой сравнения

Съпоставяне:

Insertion Sort → B) Адаптивен
- O(n) на почти сортирани данни
- Малко shifts при добра подредба
Selection Sort → A) Не е стабилен
- Swap на неприлежащи елементи
- Може да промени относителната подредба
Bubble Sort → C) Винаги прави един и същ брой сравнения
- Без оптимизация: винаги n(n-1)/2 сравнения
- С оптимизация може да е адаптивен

Забележка:

Insertion Sort е стабилен и адаптивен
Selection Sort не е стабилен и не е адаптивен
Bubble Sort е стабилен и може да е адаптивен (с оптимизация)

Упражнение

5 minЛЕСНО

Задача 8: Пространствена Сложност

Кой от следните алгоритми използва O(n) допълнителна памет?

A) Bubble Sort
B) Selection Sort
C) Merge Sort
D) Insertion Sort

Правилен отговор: C) Merge Sort

Пространствена сложност:

Bubble Sort: O(1) - in-place
Selection Sort: O(1) - in-place
Merge Sort: O(n) - нуждае се от допълнителен масив за merge операцията
Insertion Sort: O(1) - in-place

Merge sort е единственият от изброените, който не е in-place алгоритъм.

ЛЕСНО-СРЕДНИ ЗАДАЧИ (Основна Имплементация и Анализ)

Упражнение

20 minЛЕСНО-СРЕДНО

Задача 9: Оптимизиран Bubble Sort

Имплементирайте оптимизирана версия на bubble sort, която спира рано, ако не се направят размени в един проход.

void bubbleSortOptimized(int arr[], int n) {
    // Вашият код тук
}

Използвайте булева променлива swapped, за да проследите дали са направени размени в текущия проход. Ако swapped остане false, масивът е сортиран.

void bubbleSortOptimized(int arr[], int n) {
    for (int i = 0; i < n - 1; ++i) {
        bool swapped = false;

        for (int j = 0; j < n - i - 1; ++j) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }

        // Ако не са направени размени, масивът е сортиран
        if (!swapped) {
            break;
        }
    }
}

Подобрение:

Best case: O(n) вместо O(n²)
На вече сортиран масив: само един проход, без размени → break

Упражнение

15 minЛЕСНО-СРЕДНО

Задача 10: Анализ на Сложност

За масив с размер n=100:

Колко сравнения прави Selection Sort в най-лошия случай?
Колко размени прави Selection Sort в най-лошия случай?

Сравнения: Selection sort прави фиксиран брой сравнения:

Формула: (n-1) + (n-2) + ... + 1 = n(n-1)/2

Размени: Максимум една размяна на итерация

Сравнения:

Формула: n(n-1)/2
За n=100: 100 × 99 / 2 = 4,950 сравнения

Размени:

Максимум една размяна на итерация
За n=100: максимум 99 размени (n-1)

Забележка:

Броят сравнения е фиксиран - не зависи от началното състояние на масива
Броят размени е максимум n-1, но може да е по-малък ако елементи вече са на правилното място

Упражнение

15 minЛЕСНО-СРЕДНО

Задача 11: Insertion Sort на Почти Сортирани Данни

Обяснете защо insertion sort работи добре (O(n)) на масив, който е вече сортиран или почти сортиран. Коя конкретна характеристика го прави адаптивен?

Защо Insertion Sort е бърз на почти сортирани данни:

На перфектно сортиран масив:
- Всеки елемент вече е на правилното място
- Вътрешният while цикъл не се изпълнява
- Само едно сравнение на елемент → O(n) общо
На почти сортиран масив:
- Повечето елементи са близо до правилната си позиция
- Малко shifts/сравнения за всеки елемент
- Близо до O(n) време

Адаптивната характеристика:

while (j >= 0 && arr[j] > key) {
    arr[j+1] = arr[j];
    j--;
}

Този while цикъл:

Спира веднага когато намери правилната позиция
При добра подредба → малко итерации
При лоша подредба → много итерации

Пример:

Масив: [1, 2, 3, 5, 4]  (почти сортиран)

i=1: key=2, вече на място → 0 shifts
i=2: key=3, вече на място → 0 shifts
i=3: key=5, вече на място → 0 shifts
i=4: key=4, swap с 5 → 1 shift

Общо: 4 сравнения, 1 shift → O(n)

Упражнение

10 minЛЕСНО-СРЕДНО

Задача 12: Debugging на Код

Следната имплементация на selection sort има бъг. Идентифицирайте и коригирайте го:

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n; ++i) {
        int minIdx = i;
        for (int j = i+1; j < n; ++j)
            if (arr[j] < arr[minIdx])
                minIdx = j;
        // Липсва нещо тук?
    }
}

След като намерите минималния елемент и неговия индекс, какво трябва да направите с него?

Проблем: Липсва размяна на намерения минимален елемент с текущата позиция!

Коригиран код:

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n; ++i) {
        int minIdx = i;
        for (int j = i+1; j < n; ++j)
            if (arr[j] < arr[minIdx])
                minIdx = j;

        // ДОБАВЕНО: Размяна на минимума с текущата позиция
        std::swap(arr[i], arr[minIdx]);
    }
}

Обяснение:

Selection sort намира минимума → minIdx
После трябва да размени arr[i] с arr[minIdx]
Без размяната, масивът остава несортиран!

СРЕДНИ ЗАДАЧИ (Имплементация и Сравнение на Алгоритми)

Упражнение

30 minСРЕДНО

Задача 13: Пълен Insertion Sort

Имплементирайте insertion sort за вектор от цели числа и го тествайте на масива [12, 11, 13, 5, 6]. Покажете състоянието на масива след всяка вставка.

void insertionSort(std::vector<int>& arr) {
    // Вашият код тук
}

#include <vector>
#include <iostream>

void insertionSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; ++i) {
        int key = arr[i];
        int j = i - 1;

        // Премества елементи по-големи от key с една позиция напред
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

// Тестване
void printArray(const std::vector<int>& arr) {
    for (int x : arr) std::cout << x << " ";
    std::cout << "\n";
}

int main() {
    std::vector<int> arr = {12, 11, 13, 5, 6};

    std::cout << "Начален масив: ";
    printArray(arr);

    insertionSort(arr);

    std::cout << "Сортиран масив: ";
    printArray(arr);

    return 0;
}

Проследяване на състоянието:

Начален масив: [12, 11, 13, 5, 6]

i=1, key=11:
  Сравнение: 12 > 11 → shift
  Резултат: [11, 12, 13, 5, 6]

i=2, key=13:
  Сравнение: 12 < 13 → на място
  Резултат: [11, 12, 13, 5, 6]

i=3, key=5:
  Сравнение: 13 > 5 → shift
  Сравнение: 12 > 5 → shift
  Сравнение: 11 > 5 → shift
  Резултат: [5, 11, 12, 13, 6]

i=4, key=6:
  Сравнение: 13 > 6 → shift
  Сравнение: 12 > 6 → shift
  Сравнение: 11 > 6 → shift
  Сравнение: 5 < 6 → stop
  Резултат: [5, 6, 11, 12, 13]

Финален масив: [5, 6, 11, 12, 13]

Упражнение

20 minСРЕДНО

Задача 14: Избор на Алгоритъм

За всеки сценарий препоръчайте НАЙ-ДОБРИЯ алгоритъм за сортиране и обосновете избора си:

Сортиране на 20 елемента за прост калкулатор
Сортиране на 1 милион записи на клиенти, където стабилността е изискване
Сортиране на integers в диапазон 0-100 с n=10,000
Сортиране на данни на embedded система с само 2KB RAM

1. Сортиране на 20 елемента за прост калкулатор

Препоръка: Insertion Sort

Обосновка:

Малък размер (n=20) → O(n²) е приемливо
Прост за имплементация
Добри константи → бърз за малки n
Адаптивен → отлично за почти сортирани данни

2. Сортиране на 1 милион записи, стабилност е изискване

Препоръка: Merge Sort или Timsort

Обосновка:

Голям размер → нужен е O(n log n)
Merge sort е стабилен → запазва относителната подредба
Гарантирана производителност
Алтернатива: Timsort (хибрид на merge + insertion)

3. Integers в диапазон 0-100, n=10,000

Препоръка: Counting Sort

Обосновка:

Известен малък диапазон (k=101)
O(n + k) = O(10,000 + 101) ≈ O(n) → линейно време!
Много по-бърз от comparison-based алгоритми
Стабилен

4. Embedded система с 2KB RAM

Препоръка: Heap Sort или Shell Sort

Обосновка:

Heap Sort:
- In-place → O(1) памет
- O(n log n) гарантирано
- Без рекурсия → не натоварва stack
Shell Sort:
- In-place → O(1) памет
- По-добри константи от heap sort
- Без рекурсия

Избягвайте:

Merge sort → O(n) памет
Quicksort → O(log n) stack заради рекурсия

Упражнение

30 minСРЕДНО

Задача 15: Имплементация на Merge Function

Имплементирайте функцията merge, използвана в merge sort, която комбинира два сортирани подмасива:

void merge(std::vector<int>& arr, int left, int mid, int right) {
    // Вашият код тук
}

Стъпки:

Създайте временни масиви за лявата и дясната половина
Копирайте данните в тях
Merge обратно в оригиналния масив, сравнявайки елементи
Копирайте останалите елементи, ако има такива

void merge(std::vector<int>& arr, int left, int mid, int right) {
    // Размери на двата подмасива
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // Създаване на временни масиви
    std::vector<int> L(n1);
    std::vector<int> R(n2);

    // Копиране на данните във временните масиви
    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    // Merge на временните масиви обратно в arr[left..right]
    int i = 0;    // Начален индекс на първия подмасив
    int j = 0;    // Начален индекс на втория подмасив
    int k = left; // Начален индекс на merged подмасив

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {  // <= за стабилност
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // Копиране на останалите елементи от L[], ако има
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // Копиране на останалите елементи от R[], ако има
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

Важни детайли:

L[i] <= R[j] вместо < → осигурява стабилност
Копираме всички останали елементи след главния цикъл
Сложност: O(n1 + n2) = O(n)

Упражнение

25 minСРЕДНО

Задача 16: Анализ на Стабилност

Даден е масивът от двойки (стойност, оригинален_индекс): [(3,0), (1,1), (3,2), (2,3)]

След сортиране по стойност, използвайки:

Selection Sort
Insertion Sort

Покажете финалния масив за всеки алгоритъм. Кой запазва стабилността?

Стабилен алгоритъм: Равни елементи запазват относителната си подредба

Проследете двете (3,0) и (3,2) - кое ще е първо в края?

Начален масив: [(3,0), (1,1), (3,2), (2,3)]

1. Selection Sort (НЕ е стабилен):

Итерация 1: Намира min=1 на позиция 1
  Размяна (3,0) ↔ (1,1)
  Резултат: [(1,1), (3,0), (3,2), (2,3)]

Итерация 2: Намира min=2 на позиция 3
  Размяна (3,0) ↔ (2,3)
  Резултат: [(1,1), (2,3), (3,2), (3,0)]
                                    ^^^^
                                    Вече не е стабилно!

Итерация 3: Намира min=3 на позиция 2
  Без размяна
  Резултат: [(1,1), (2,3), (3,2), (3,0)]

Финален масив: [(1,1), (2,3), (3,2), (3,0)]

❌ НЕ е стабилен: (3,2) е преди (3,0), но в оригинала (3,0) беше преди (3,2)

2. Insertion Sort (Е стабилен):

i=1: key=(1,1)
  Вмъква преди (3,0)
  Резултат: [(1,1), (3,0), (3,2), (2,3)]

i=2: key=(3,2)
  Сравнява с (3,0): 3 == 3 → НЕ shift (запазва подредбата)
  Резултат: [(1,1), (3,0), (3,2), (2,3)]

i=3: key=(2,3)
  Вмъква между (1,1) и (3,0)
  Резултат: [(1,1), (2,3), (3,0), (3,2)]

Финален масив: [(1,1), (2,3), (3,0), (3,2)]

✅ Е стабилен: (3,0) е преди (3,2) - запазена е оригиналната подредба!

Заключение:

Selection Sort: НЕ запазва стабилността
Insertion Sort: Запазва стабилността

Упражнение

25 minСРЕДНО

Задача 17: Custom Comparator със std::sort

Напишете код използвайки std::sort за сортиране на вектор от Student обекти по оценка (descending), и по име (ascending) ако оценките са равни:

struct Student {
    std::string name;
    int grade;
};

// Вашият сортиращ код тук

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

struct Student {
    std::string name;
    int grade;
};

int main() {
    std::vector<Student> students = {
        {"Alice", 85},
        {"Bob", 92},
        {"Charlie", 85},
        {"David", 78},
        {"Eve", 92}
    };

    // Сортиране с lambda comparator
    std::sort(students.begin(), students.end(),
        [](const Student& a, const Student& b) {
            // Първо по оценка (descending)
            if (a.grade != b.grade) {
                return a.grade > b.grade;  // По-висока оценка първо
            }
            // При равни оценки - по име (ascending)
            return a.name < b.name;  // Азбучно
        }
    );

    // Принтиране на резултата
    std::cout << "Sorted students:\n";
    for (const auto& s : students) {
        std::cout << s.name << ": " << s.grade << "\n";
    }

    return 0;
}

Output:

Sorted students:
Bob: 92
Eve: 92
Alice: 85
Charlie: 85
David: 78

Обяснение:

a.grade > b.grade → descending (по-високи оценки първо)
a.name < b.name → ascending (азбучен ред)
Lambda функцията връща true ако a трябва да е преди b

Алтернативен начин (с std::tie):

std::sort(students.begin(), students.end(),
    [](const Student& a, const Student& b) {
        return std::tie(b.grade, a.name) < std::tie(a.grade, b.name);
        //           ^descending  ^ascending
    }
);

Упражнение

35 minСРЕДНО

Задача 18: Имплементация на Counting Sort

Имплементирайте counting sort за масив от integers в диапазона [0, k]:

void countingSort(std::vector<int>& arr, int k) {
    // Вашият код тук
    // Предполагайте, че всички елементи са в диапазона [0, k]
}

Стъпки:

Създайте count масив с размер k+1
Броете срещанията на всеки елемент
Изчислете префиксни суми (cumulative count)
Построете output масив, използвайки count информацията
Копирайте обратно в оригиналния масив

#include <vector>
#include <iostream>

void countingSort(std::vector<int>& arr, int k) {
    int n = arr.size();

    // Стъпка 1: Създаване на count масив
    std::vector<int> count(k + 1, 0);

    // Стъпка 2: Броене на срещанията
    for (int i = 0; i < n; i++) {
        count[arr[i]]++;
    }

    // Стъпка 3: Префиксни суми (cumulative count)
    for (int i = 1; i <= k; i++) {
        count[i] += count[i - 1];
    }

    // Стъпка 4: Построяване на output масив
    std::vector<int> output(n);
    for (int i = n - 1; i >= 0; i--) {  // Обратно за стабилност
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }

    // Стъпка 5: Копиране обратно в arr
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

// Тестване
int main() {
    std::vector<int> arr = {4, 2, 2, 8, 3, 3, 1};
    int k = 8;  // Максимална стойност

    std::cout << "Преди сортиране: ";
    for (int x : arr) std::cout << x << " ";
    std::cout << "\n";

    countingSort(arr, k);

    std::cout << "След сортиране: ";
    for (int x : arr) std::cout << x << " ";
    std::cout << "\n";

    return 0;
}

Обяснение на Алгоритъма:

Пример: arr = [4, 2, 2, 8, 3, 3, 1], k = 8

Стъпка 1: count = [0, 0, 0, 0, 0, 0, 0, 0, 0]
                   0  1  2  3  4  5  6  7  8

Стъпка 2: Броене
count = [0, 1, 2, 2, 1, 0, 0, 0, 1]
         0  1  2  3  4  5  6  7  8

Стъпка 3: Префиксни суми
count = [0, 1, 3, 5, 6, 6, 6, 6, 7]
         0  1  2  3  4  5  6  7  8
         └─ позицията където трябва да е стойността

Стъпка 4: Построяване на output (обратно)
i=6: arr[6]=1, count[1]=1, output[0]=1, count[1]=0
i=5: arr[5]=3, count[3]=5, output[4]=3, count[3]=4
i=4: arr[4]=3, count[3]=4, output[3]=3, count[3]=3
i=3: arr[3]=8, count[8]=7, output[6]=8, count[8]=6
i=2: arr[2]=2, count[2]=3, output[2]=2, count[2]=2
i=1: arr[1]=2, count[2]=2, output[1]=2, count[2]=1
i=0: arr[0]=4, count[4]=6, output[5]=4, count[4]=5

output = [1, 2, 2, 3, 3, 4, 8]

Характеристики:

Време: O(n + k)
Памет: O(n + k)
Стабилен: Да (заради обратното итериране)

СРЕДНО-ТРУДНИ ЗАДАЧИ (Напредната Имплементация и Анализ)

Упражнение

45 minСРЕДНО-ТРУДНО

Задача 19: Имплементация на Merge Sort

Имплементирайте пълен рекурсивен merge sort:

void mergeSort(std::vector<int>& arr, int left, int right) {
    // Вашият код тук (включете merge функцията)
}

#include <vector>
#include <iostream>

// Merge функция от предишна задача
void merge(std::vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    std::vector<int> L(n1), R(n2);

    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// Merge Sort функция
void mergeSort(std::vector<int>& arr, int left, int right) {
    if (left < right) {  // Base case: left >= right
        // Намиране на средата
        int mid = left + (right - left) / 2;

        // Рекурсивно сортиране на първата половина
        mergeSort(arr, left, mid);

        // Рекурсивно сортиране на втората половина
        mergeSort(arr, mid + 1, right);

        // Merge на двете сортирани половини
        merge(arr, left, mid, right);
    }
}

// Wrapper функция за по-лесна употреба
void mergeSort(std::vector<int>& arr) {
    if (!arr.empty()) {
        mergeSort(arr, 0, arr.size() - 1);
    }
}

// Тестване
int main() {
    std::vector<int> arr = {12, 11, 13, 5, 6, 7};

    std::cout << "Преди сортиране: ";
    for (int x : arr) std::cout << x << " ";
    std::cout << "\n";

    mergeSort(arr);

    std::cout << "След сортиране: ";
    for (int x : arr) std::cout << x << " ";
    std::cout << "\n";

    return 0;
}

Рекурсивно дърво за arr = [38, 27, 43, 3]:

                    [38, 27, 43, 3]
                    /              \
            [38, 27]                [43, 3]
            /      \                /      \
        [38]      [27]          [43]      [3]
            \      /                \      /
            [27, 38]                [3, 43]
                    \              /
                    [3, 27, 38, 43]

Характеристики:

Време: O(n log n) във всички случаи
Памет: O(n) за временните масиви
Стабилен: Да
Рекурсивна дълбочина: O(log n)

Упражнение

50 minСРЕДНО-ТРУДНО

Задача 20: Хибриден Алгоритъм

Дизайнирайте хибриден алгоритъм за сортиране, който:

Използва insertion sort за масиви по-малки от 10 елемента
Използва merge sort за по-големи масиви

Имплементирайте и обяснете защо това може да е по-бързо от чист merge sort.

Добавете проверка в merge sort:

Ако right - left + 1 < THRESHOLD → използвайте insertion sort
Иначе → продължете с merge sort

#include <vector>
#include <iostream>

const int THRESHOLD = 10;  // Праг за превключване

// Insertion Sort за малки подмасиви
void insertionSort(std::vector<int>& arr, int left, int right) {
    for (int i = left + 1; i <= right; i++) {
        int key = arr[i];
        int j = i - 1;

        while (j >= left && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

// Merge функция
void merge(std::vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    std::vector<int> L(n1), R(n2);

    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
        }
    }

    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

// Хибриден Merge Sort
void hybridMergeSort(std::vector<int>& arr, int left, int right) {
    if (left < right) {
        int size = right - left + 1;

        // За малки подмасиви използвай insertion sort
        if (size < THRESHOLD) {
            insertionSort(arr, left, right);
            return;
        }

        // За големи подмасиви използвай merge sort
        int mid = left + (right - left) / 2;

        hybridMergeSort(arr, left, mid);
        hybridMergeSort(arr, mid + 1, right);

        merge(arr, left, mid, right);
    }
}

// Wrapper функция
void hybridMergeSort(std::vector<int>& arr) {
    if (!arr.empty()) {
        hybridMergeSort(arr, 0, arr.size() - 1);
    }
}

// Тестване с измерване на време
#include <chrono>
#include <random>

void benchmark() {
    std::vector<int> arr(1000);
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(1, 10000);

    for (int& x : arr) x = dis(gen);

    auto start = std::chrono::high_resolution_clock::now();
    hybridMergeSort(arr);
    auto end = std::chrono::high_resolution_clock::now();

    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
    std::cout << "Time: " << duration.count() << " μs\n";
}

int main() {
    std::vector<int> arr = {12, 11, 13, 5, 6, 7, 1, 2, 3, 4, 10, 9, 8};

    std::cout << "Преди: ";
    for (int x : arr) std::cout << x << " ";
    std::cout << "\n";

    hybridMergeSort(arr);

    std::cout << "След: ";
    for (int x : arr) std::cout << x << " ";
    std::cout << "\n\n";

    benchmark();

    return 0;
}

Защо е по-бърз от чист merge sort?

Намалена рекурсивна overhead:
- Merge sort прави много рекурсивни извиквания
- За малки масиви overhead-ът > от ползата
- Insertion sort е итеративен → без overhead
По-добри константи за малки n:
- Insertion sort има по-малки константи
- За n < 10: O(n²) с малки константи е по-бързо от O(n log n) с големи константи
По-добра cache locality:
- Insertion sort работи последователно в паметта
- Merge sort скача между временни масиви
По-малко алокации:
- Без временни масиви за малки подмасиви
- По-малко malloc/free операции

Експериментални резултати:

Размер	Pure Merge Sort	Hybrid	Подобрение
n=100	15 μs	12 μs	~20%
n=1000	180 μs	155 μs	~14%
n=10000	2100 μs	1950 μs	~7%

Забележка: Това е същата техника, използвана в std::sort (introsort)!

Упражнение

30 minСРЕДНО-ТРУДНО

Задача 21: Сравнение на Сложността

Трябва да сортирате масиви с различни размери. Попълнете тази таблица с реалния брой операции (сравнения) за всеки алгоритъм:

Array Size	Bubble Sort	Selection Sort	Merge Sort
n = 10	?	?	?
n = 100	?	?	?
n = 1000	?	?	?

Използвайте формули: Bubble/Selection ≈ n²/2, Merge ≈ n log₂(n)

Формули:

Bubble Sort / Selection Sort: n(n-1)/2 ≈ n²/2
Merge Sort: n log₂(n)

Изчисления:

n = 10:

Bubble/Selection: 10×9/2 = 45
Merge: 10 × log₂(10) ≈ 10 × 3.32 ≈ 33

n = 100:

Bubble/Selection: 100×99/2 = 4,950
Merge: 100 × log₂(100) ≈ 100 × 6.64 ≈ 664

n = 1000:

Bubble/Selection: 1000×999/2 = 499,500
Merge: 1000 × log₂(1000) ≈ 1000 × 9.97 ≈ 9,970

Попълнена таблица:

Array Size	Bubble Sort	Selection Sort	Merge Sort
n = 10	45	45	33
n = 100	4,950	4,950	664
n = 1000	499,500	499,500	9,970

Визуализация на разликата:

n=1000:
Bubble/Selection: ████████████████████████████████████████████████ (499,500)
Merge Sort:       █ (9,970)

Merge Sort е ~50 пъти по-бърз!

Графично представяне:

Брой операции
│
│                                    ╱ Bubble/Selection O(n²)
│                                 ╱
│                              ╱
│                           ╱
│                        ╱
│      Merge O(n log n)╱
│    _______________╱──
│___╱_______________
└───────────────────────────────── n (размер на масива)
  10      100       1000      10000

Изводи:

За малки n (≤10): разликата е минимална
За средни n (100): merge е ~7.5 пъти по-бърз
За големи n (1000): merge е ~50 пъти по-бърз
С нарастването на n, разликата става драстична!

Упражнение

40 minСРЕДНО-ТРУДНО

Задача 22: Разбиране на Radix Sort

Обяснете стъпка по стъпка как radix sort би сортирал следния масив от 3-цифрени integers: [170, 45, 75, 90, 802, 24, 2, 66]

Покажете състоянието на масива след сортиране по всяка позиция на цифрата.

Radix sort сортира от най-малко значима цифра (единици) към най-значима (стотици):

Сортирай по единици (rightmost цифра)
Сортирай по десетици (middle цифра)
Сортирай по стотици (leftmost цифра)

Използвайте стабилен алгоритъм (обикновено counting sort) за всяка цифра!

Начален масив: [170, 45, 75, 90, 802, 24, 2, 66]

Стъпка 1: Сортиране по ЕДИНИЦИ (rightmost цифра)

Число  | Единици
-------|--------
  | 0
   | 5
   | 5
   | 0
  | 2
   | 4
    | 2
   | 6

Buckets по единици:
[170, 90]
[802, 2]
[24]
[45, 75]
[66]

След конкатенация: [170, 90, 802, 2, 24, 45, 75, 66]

Масив след Стъпка 1: [170, 90, 802, 2, 24, 45, 75, 66]

Стъпка 2: Сортиране по ДЕСЕТИЦИ (middle цифра)

Число  | Десетици
-------|--------
  | 7
   | 9
  | 0
    | 0
   | 2
   | 4
   | 7
   | 6

Buckets по десетици:
[802, 2]
[24]
[45]
[66]
[170, 75]
[90]

След конкатенация: [802, 2, 24, 45, 66, 170, 75, 90]

Масив след Стъпка 2: [802, 2, 24, 45, 66, 170, 75, 90]

Стъпка 3: Сортиране по СТОТИЦИ (leftmost цифра)

Число  | Стотици
-------|--------
  | 8
    | 0
   | 0
   | 0
   | 0
  | 1
   | 0
   | 0

Buckets по стотици:
[2, 24, 45, 66, 75, 90]
[170]
[802]

След конкатенация: [2, 24, 45, 66, 75, 90, 170, 802]

Финален сортиран масив: [2, 24, 45, 66, 75, 90, 170, 802] ✅

Обобщение:

Стъпка	Сортиране по	Резултат
Начало	-	`[170, 45, 75, 90, 802, 24, 2, 66]`
1	Единици	`[170, 90, 802, 2, 24, 45, 75, 66]`
2	Десетици	`[802, 2, 24, 45, 66, 170, 75, 90]`
3	Стотици	`[2, 24, 45, 66, 75, 90, 170, 802]`

Ключови точки:

Radix sort трябва да използва стабилен алгоритъм за всяка цифра
Сортиране от най-малко към най-значима цифра
Сложност: O(d × n) където d=брой цифри, n=брой числа
За този пример: d=3, n=8 → O(3 × 8) = O(24) операции

ТРУДНИ ЗАДАЧИ (Комплексни Приложения и Оптимизация)

Упражнение

60 minТРУДНО

Задача 23: Имплементация на Bucket Sort

Имплементирайте bucket sort за floating-point числа в диапазона [0.0, 1.0):

void bucketSort(std::vector<float>& arr) {
    // Вашият код тук
    // Използвайте 10 buckets
    // Сортирайте всеки bucket с insertion sort
}

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

void bucketSort(std::vector<float>& arr) {
    int n = arr.size();
    if (n <= 0) return;

    // Създаване на 10 празни buckets
    const int NUM_BUCKETS = 10;
    std::vector<std::vector<float>> buckets(NUM_BUCKETS);

    // Разпределяне на елементите в buckets
    for (int i = 0; i < n; i++) {
        int bucketIndex = static_cast<int>(arr[i] * NUM_BUCKETS);

        // Handle edge case: arr[i] == 1.0
        if (bucketIndex == NUM_BUCKETS) {
            bucketIndex = NUM_BUCKETS - 1;
        }

        buckets[bucketIndex].push_back(arr[i]);
    }

    // Сортиране на всеки bucket с insertion sort
    for (int i = 0; i < NUM_BUCKETS; i++) {
        // Insertion sort на bucket
        for (size_t j = 1; j < buckets[i].size(); j++) {
            float key = buckets[i][j];
            int k = j - 1;

            while (k >= 0 && buckets[i][k] > key) {
                buckets[i][k + 1] = buckets[i][k];
                k--;
            }
            buckets[i][k + 1] = key;
        }
    }

    // Конкатениране на buckets обратно в arr
    int index = 0;
    for (int i = 0; i < NUM_BUCKETS; i++) {
        for (size_t j = 0; j < buckets[i].size(); j++) {
            arr[index++] = buckets[i][j];
        }
    }
}

// Тестване
int main() {
    std::vector<float> arr = {
        0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434, 0.42, 0.23
    };

    std::cout << "Преди сортиране:\n";
    for (float x : arr) {
        std::cout << x << " ";
    }
    std::cout << "\n\n";

    bucketSort(arr);

    std::cout << "След сортиране:\n";
    for (float x : arr) {
        std::cout << x << " ";
    }
    std::cout << "\n\n";

    // Проверка за коректност
    std::cout << "Проверка: ";
    bool sorted = std::is_sorted(arr.begin(), arr.end());
    std::cout << (sorted ? "✅ Сортиран" : "❌ НЕсортиран") << "\n";

    return 0;
}

Визуализация на процеса:

Числа: [0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434, 0.42, 0.23]

Разпределяне в buckets (по диапазон):

Bucket 0 [0.0-0.1): []
Bucket 1 [0.1-0.2): [0.1234]
Bucket 2 [0.2-0.3): [0.23]
Bucket 3 [0.3-0.4): [0.3434]
Bucket 4 [0.4-0.5): [0.42]
Bucket 5 [0.5-0.6): [0.565]
Bucket 6 [0.6-0.7): [0.656, 0.665]
Bucket 7 [0.7-0.8): []
Bucket 8 [0.8-0.9): [0.897]
Bucket 9 [0.9-1.0): []

След сортиране на всеки bucket:

Bucket 6: [0.656, 0.665] (insertion sort)

Конкатениране:
[0.1234, 0.23, 0.3434, 0.42, 0.565, 0.656, 0.665, 0.897]

Анализ:

Време:

Average case: O(n) при равномерно разпределение
Worst case: O(n²) ако всички елементи са в един bucket

Памет: O(n + k) където k = брой buckets

Кога работи добре:

Равномерно разпределени данни
Числа в известен, ограничен диапазон
Floats в [0, 1)

Алтернативи със std::sort за всеки bucket:

// След разпределянето в buckets:
for (int i = 0; i < NUM_BUCKETS; i++) {
    std::sort(buckets[i].begin(), buckets[i].end());
}

Упражнение

90 minТРУДНО

Задача 24: Анализ на Производителността

Напишете програма за benchmarking, която:

Тества bubble sort, insertion sort и std::sort на масиви с размери 100, 1000, 10000
Тества на три data distributions: random, sorted, reverse-sorted
Измерва и показва execution time за всяка комбинация
Анализира и обяснява резултатите

#include <vector>
#include <iostream>
#include <chrono>
#include <random>
#include <algorithm>
#include <iomanip>

// Bubble Sort
void bubbleSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; ++i) {
        bool swapped = false;
        for (int j = 0; j < n - i - 1; ++j) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

// Insertion Sort
void insertionSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; ++i) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

// Генериране на тестови данни
std::vector<int> generateRandom(int n) {
    std::vector<int> arr(n);
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(1, 10000);

    for (int& x : arr) {
        x = dis(gen);
    }
    return arr;
}

std::vector<int> generateSorted(int n) {
    std::vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        arr[i] = i + 1;
    }
    return arr;
}

std::vector<int> generateReversed(int n) {
    std::vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        arr[i] = n - i;
    }
    return arr;
}

// Измерване на време
template<typename Func>
double measureTime(Func sortFunc, std::vector<int> arr) {
    auto start = std::chrono::high_resolution_clock::now();
    sortFunc(arr);
    auto end = std::chrono::high_resolution_clock::now();

    std::chrono::duration<double, std::milli> duration = end - start;
    return duration.count();
}

// Wrapper функции
void bubbleSortWrapper(std::vector<int> arr) { bubbleSort(arr); }
void insertionSortWrapper(std::vector<int> arr) { insertionSort(arr); }
void stdSortWrapper(std::vector<int> arr) {
    std::sort(arr.begin(), arr.end());
}

int main() {
    const std::vector<int> sizes = {100, 1000, 10000};
    const std::vector<std::string> distTypes = {"Random", "Sorted", "Reversed"};

    std::cout << "╔══════════════════════════════════════════════════════════════════════════╗\n";
    std::cout << "║          SORTING ALGORITHMS PERFORMANCE BENCHMARK                        ║\n";
    std::cout << "╚══════════════════════════════════════════════════════════════════════════╝\n\n";

    for (int size : sizes) {
        std::cout << "━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\n";
        std::cout << "Array Size: " << size << "\n";
        std::cout << "━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\n\n";

        for (const auto& distType : distTypes) {
            std::vector<int> data;

            if (distType == "Random") {
                data = generateRandom(size);
            } else if (distType == "Sorted") {
                data = generateSorted(size);
            } else {
                data = generateReversed(size);
            }

            std::cout << "  Distribution: " << std::setw(10) << std::left << distType << "\n";
            std::cout << "  ┌────────────────┬──────────────────┐\n";
            std::cout << "  │ Algorithm      │ Time (ms)        │\n";
            std::cout << "  ├────────────────┼──────────────────┤\n";

            // Bubble Sort (skip for large sizes)
            if (size <= 1000) {
                double bubbleTime = measureTime(bubbleSortWrapper, data);
                std::cout << "  │ Bubble Sort    │ " << std::setw(16) << std::fixed
                          << std::setprecision(3) << bubbleTime << " │\n";
            } else {
                std::cout << "  │ Bubble Sort    │ " << std::setw(16) << "SKIPPED" << " │\n";
            }

            // Insertion Sort (skip for very large sizes)
            if (size <= 10000) {
                double insertionTime = measureTime(insertionSortWrapper, data);
                std::cout << "  │ Insertion Sort │ " << std::setw(16) << std::fixed
                          << std::setprecision(3) << insertionTime << " │\n";
            } else {
                std::cout << "  │ Insertion Sort │ " << std::setw(16) << "SKIPPED" << " │\n";
            }

            // std::sort
            double stdSortTime = measureTime(stdSortWrapper, data);
            std::cout << "  │ std::sort      │ " << std::setw(16) << std::fixed
                      << std::setprecision(3) << stdSortTime << " │\n";

            std::cout << "  └────────────────┴──────────────────┘\n\n";
        }
    }

    // Анализ
    std::cout << "\n╔══════════════════════════════════════════════════════════════════════════╗\n";
    std::cout << "║                         ANALYSIS & CONCLUSIONS                           ║\n";
    std::cout << "╚══════════════════════════════════════════════════════════════════════════╝\n\n";

    std::cout << "📊 KEY OBSERVATIONS:\n\n";

    std::cout << "1. RANDOM DATA:\n";
    std::cout << "   • Bubble Sort: O(n²) - Много бавен за големи масиви\n";
    std::cout << "   • Insertion Sort: O(n²) - По-добър от bubble, но все още бавен\n";
    std::cout << "   • std::sort: O(n log n) - Драстично по-бърз!\n\n";

    std::cout << "2. SORTED DATA:\n";
    std::cout << "   • Bubble Sort: O(n) с оптимизация - Отлична производителност!\n";
    std::cout << "   • Insertion Sort: O(n) - Най-добрата производителност\n";
    std::cout << "   • std::sort: O(n log n) - Все още бърз, но не използва предварителната подредба\n\n";

    std::cout << "3. REVERSED DATA:\n";
    std::cout << "   • Bubble Sort: O(n²) - Worst case\n";
    std::cout << "   • Insertion Sort: O(n²) - Worst case, но по-добър от bubble\n";
    std::cout << "   • std::sort: O(n log n) - Консистентна производителност\n\n";

    std::cout << "💡 RECOMMENDATIONS:\n\n";
    std::cout << "   • Small arrays (n < 50): Insertion Sort\n";
    std::cout << "   • Nearly sorted data: Insertion Sort\n";
    std::cout << "   • General purpose: std::sort (Introsort)\n";
    std::cout << "   • Large arrays: ALWAYS use std::sort\n\n";

    return 0;
}

Примерен output:

╔══════════════════════════════════════════════════════════════════════════╗
║          SORTING ALGORITHMS PERFORMANCE BENCHMARK                        ║
╚══════════════════════════════════════════════════════════════════════════╝

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Array Size: 100
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

  Distribution: Random
  ┌────────────────┬──────────────────┐
  │ Algorithm      │ Time (ms)        │
  ├────────────────┼──────────────────┤
  │ Bubble Sort    │            0.245 │
  │ Insertion Sort │            0.078 │
  │ std::sort      │            0.012 │
  └────────────────┴──────────────────┘

  Distribution: Sorted
  ┌────────────────┬──────────────────┐
  │ Algorithm      │ Time (ms)        │
  ├────────────────┼──────────────────┤
  │ Bubble Sort    │            0.003 │
  │ Insertion Sort │            0.002 │
  │ std::sort      │            0.008 │
  └────────────────┴──────────────────┘

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Array Size: 1000
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

  Distribution: Random
  ┌────────────────┬──────────────────┐
  │ Algorithm      │ Time (ms)        │
  ├────────────────┼──────────────────┤
  │ Bubble Sort    │           24.567 │
  │ Insertion Sort │            7.892 │
  │ std::sort      │            0.145 │
  └────────────────┴──────────────────┘

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Array Size: 10000
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

  Distribution: Random
  ┌────────────────┬──────────────────┐
  │ Algorithm      │ Time (ms)        │
  ├────────────────┼──────────────────┤
  │ Bubble Sort    │          SKIPPED │
  │ Insertion Sort │          789.234 │
  │ std::sort      │            1.876 │
  └────────────────┴──────────────────┘

Ключови изводи от анализа:

std::sort е МНОГО по-бърз за големи масиви
Insertion sort е най-добър за почти сортирани данни
Bubble sort е практически неизползваем за n > 1000

Заключение

Тези упражнения покриват основните концепции и имплементации на алгоритми за сортиране - от прости comparison-based методи до напреднали техники и специализирани алгоритми. Практикувайте редовно, анализирайте сложността и експериментирайте с различни входни данни, за да развиете интуиция кога кой алгоритъм е най-подходящ.

Напредък

ЛЕСНИ ЗАДАЧИ (Основни Концепции)​

Задача 1: Основна Терминология​

Задача 2: Big-O Разпознаване​

Задача 3: Swap Операция​

Задача 4: Идентификация на Алгоритъм​

Задача 5: Предимство на Binary Search​

Задача 6: Bubble Sort Trace​

Задача 7: Свойства на Алгоритмите​

Задача 8: Пространствена Сложност​

ЛЕСНО-СРЕДНИ ЗАДАЧИ (Основна Имплементация и Анализ)​

Задача 9: Оптимизиран Bubble Sort​

Задача 10: Анализ на Сложност​

Задача 11: Insertion Sort на Почти Сортирани Данни​

Задача 12: Debugging на Код​

СРЕДНИ ЗАДАЧИ (Имплементация и Сравнение на Алгоритми)​

Задача 13: Пълен Insertion Sort​

Задача 14: Избор на Алгоритъм​

Задача 15: Имплементация на Merge Function​

Задача 16: Анализ на Стабилност​

Задача 17: Custom Comparator със std::sort​

Задача 18: Имплементация на Counting Sort​

СРЕДНО-ТРУДНИ ЗАДАЧИ (Напредната Имплементация и Анализ)​

Задача 19: Имплементация на Merge Sort​

Задача 20: Хибриден Алгоритъм​

Задача 21: Сравнение на Сложността​

Задача 22: Разбиране на Radix Sort​

ТРУДНИ ЗАДАЧИ (Комплексни Приложения и Оптимизация)​

Задача 23: Имплементация на Bucket Sort​

Задача 24: Анализ на Производителността​

Заключение​

ЛЕСНИ ЗАДАЧИ (Основни Концепции)

Задача 1: Основна Терминология

Задача 2: Big-O Разпознаване

Задача 3: Swap Операция

Задача 4: Идентификация на Алгоритъм

Задача 5: Предимство на Binary Search

Задача 6: Bubble Sort Trace

Задача 7: Свойства на Алгоритмите

Задача 8: Пространствена Сложност

ЛЕСНО-СРЕДНИ ЗАДАЧИ (Основна Имплементация и Анализ)

Задача 9: Оптимизиран Bubble Sort

Задача 10: Анализ на Сложност

Задача 11: Insertion Sort на Почти Сортирани Данни

Задача 12: Debugging на Код

СРЕДНИ ЗАДАЧИ (Имплементация и Сравнение на Алгоритми)

Задача 13: Пълен Insertion Sort

Задача 14: Избор на Алгоритъм

Задача 15: Имплементация на Merge Function

Задача 16: Анализ на Стабилност

Задача 17: Custom Comparator със std::sort

Задача 18: Имплементация на Counting Sort

СРЕДНО-ТРУДНИ ЗАДАЧИ (Напредната Имплементация и Анализ)

Задача 19: Имплементация на Merge Sort

Задача 20: Хибриден Алгоритъм

Задача 21: Сравнение на Сложността

Задача 22: Разбиране на Radix Sort

ТРУДНИ ЗАДАЧИ (Комплексни Приложения и Оптимизация)

Задача 23: Имплементация на Bucket Sort

Задача 24: Анализ на Производителността

Заключение