Алгоритми за Сортиране в C++: От Основи до Напреднали Техники

▶⚡ Накратко

За Изпита

🎯Учебни Цели

След края на тази лекция вие ще можете да:

• ✓Разбиране на фундаментални концепции за сортиране - стабилност, in-place сортиране, comparison-based vs non-comparison-based алгоритми
• ✓Имплементация и анализ на прости алгоритми за сортиране - bubble sort, selection sort, insertion sort
• ✓Разбиране на времева и пространствена сложност на различни алгоритми за сортиране
• ✓Имплементация на divide-and-conquer алгоритми - merge sort и quicksort
• ✓Избор на подходящ алгоритъм за сортиране според контекста и изискванията

---

1. Въведение: Защо Сортирането е Важно?

Сортирането е фундаментална операция в компютърните науки - почти всяка голяма софтуерна система, от бази данни до операционни системи и търсачки, разчита на бързо и надеждно сортиране за ефективно управление на данни.

💡Защо сортирането е толкова важно?

Подобряване на производителността:

• Сортираните данни позволяват бързи алгоритми за търсене като binary search (O(log n)) срещу linear search (O(n))
• При 1 милион сортирани елемента: ~20 сравнения (binary search) срещу до 1 милион (linear search)!

Реални приложения:

• Бази данни индексират и оптимизират заявки чрез сортиране
• Търсачки сортират/рангират резултати по релевантност, дата и др.
• Разпределение на ресурси, мрежова маршрутизация, изчислителна биология - всичко се базира на сортиране

ℹ️Избор на Алгоритъм

Правилният алгоритъм може да направи софтуера ви бърз и отзивчив; грешният води до бавни, неотзивчиви програми, особено при големи данни.

Прогресия на Обучението

В тази лекция ще започнем с прости, интуитивни алгоритми за сортиране, ще преминем към напреднали техники и след това ще разгледаме специализирани алгоритми, които използват свойства на данните за още по-добра производителност.

---

2. Prerequisite: Основни Програмни Концепции

Масиви: Колекции с фиксиран размер, достъпни чрез индекс (arr[i])

Вектори (std::vector<T>): Динамични масиви (могат да растат/намаляват), част от STL

• Операции: .size(), .push_back(), достъп чрез operator[] или .at(i)

#include <vector>
std::vector<int> vec = {5, 2, 8, 1};
int size = vec.size();  // 4
vec.push_back(3);       // добавя 3 в края

Сравнения: Използват се <, >, ==, <=, >= за сравнение на елементи

Размяна (swap): Размяна на два елемента - ръчно или чрез std::swap(a, b)

int a = 10, b = 5;
std::swap(a, b);  // Сега a=5, b=10

// За масиви:
std::swap(arr[i], arr[j]);

Big-O Нотация: Описва скоростта на растеж при увеличаване на входа

• O(1): Константна
• O(n): Линейна
• O(n²): Квадратична (често от вложени цикли)
• O(n log n): Линеаритмична (често от divide-and-conquer)

Идентифициране на Сложност:

• Един цикъл = O(n)
• Вложени цикли = O(n²)

Пространствена Сложност: Колко допълнителна памет се използва (auxiliary space)

Вложени Цикли: Броят на общите операции = произведение на размерите на циклите

Рекурсия: Функция извиква себе си за решаване на по-малки подпроблеми

• Важно: base case (условие за спиране) и recursive case (рекурсивно извикване)

// Пример за рекурсия
int factorial(int n) {
    if (n <= 1) return 1;        // base case
    return n * factorial(n - 1); // recursive case
}

---

3. Фундаменти на Сортирането

Какво е Сортиране? Ключови Свойства

ℹ️Определение

Сортиране: Пренареждане на данни в определен ред (възходящ, низходящ или custom)

🎯 Стабилно Сортиране (Stable Sort)

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

// Преди: [(3,a), (1,b), (3,c), (2,d)]
// След стабилно сортиране: [(1,b), (2,d), (3,a), (3,c)]
// ↑ 3,a е преди 3,c (запазена оригинална подредба)

💾 In-Place Сортиране

Сортира данните без допълнителна памет пропорционална на входа (O(1) space).

// Bubble sort е in-place
// Merge sort НЕ е in-place (използва O(n) памет)

📈 Адаптивно Сортиране

Става по-бързо когато данните са вече частично сортирани.

// Insertion sort е адаптивен
// На почти сортиран масив: O(n)
// На random масив: O(n²)

⚖️ Comparison-Based

Използва само сравнения между елементи. Долна граница: Ω(n log n).

// Bubble, Selection, Insertion, Merge, Quick, Heap
// Всички са comparison-based

Типове Алгоритми за Сортиране

❌

Comparison-Based

**Характеристики:** - Използват само сравнения между елементи - Теоретична долна граница: Ω(n log n) - Примери: bubble, selection, insertion, quicksort, merge sort, heapsort **Предимства:** - Работят с всякакви сравними типове данни - Универсални **Недостатъци:** - Не могат да бъдат по-бързи от O(n log n) в общия случай

✅

Non-Comparison-Based

**Характеристики:** - Използват свойства на данните (напр. диапазон на стойности) - Могат да постигнат O(n) при определени условия - Примери: counting sort, radix sort, bucket sort **Предимства:** - Могат да превишат O(n log n) границата - Много бързи при правилни условия **Недостатъци:** - Ограничени до специфични типове данни - Не винаги приложими

Разбиране на Класовете Сложност

🟢 Best Case

Най-малко операции (напр. вече сортиран масив)

🟡 Average Case

Очаквана производителност при случайни входове

🔴 Worst Case

Максимален брой операции (напр. обратно сортиран масив)

⚠️Важно!

Разпределението на данните има значение! Някои алгоритми (insertion, bubble с оптимизация) могат да бъдат много по-бързи на почти сортирани данни.

---

4. Прости Comparison-Based Алгоритми

4.1 Bubble Sort

ℹ️Концепция

Многократно размяна на съседни елементи, ако са в грешен ред. Големите елементи "изплуват" към края с всяка итерация.

Имплементация:

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

Проверка дали са направени размени в итерация; ако не - излизане (превръща best case в O(n)):

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) (оптимизиран)
Average Case	O(n²)
Worst Case	O(n²)
Space	O(1)
Stable	✅ Да
In-Place	✅ Да
Adaptive	✅ Да (оптимизиран)

---

4.2 Selection Sort

ℹ️Концепция

Намиране на минимума от несортираната част, преместване в правилната позиция. Винаги прави един и същ брой сравнения независимо от входа.

Имплементация:

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n-1; ++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 НЕ е стабилен - може да размени нееднакви равни елементи (swap на неприлежащи елементи).

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

Сложност	Стойност
Best Case	O(n²)
Average Case	O(n²)
Worst Case	O(n²)
Space	O(1)
Stable	❌ Не
In-Place	✅ Да
Adaptive	❌ Не

---

4.3 Insertion Sort

ℹ️Концепция

Вмъкване на всеки нов елемент на правилното му място сред вече сортираните елементи. Аналогия: сортиране на карти в ръка.

Имплементация:

void insertionSort(int arr[], int n) {
    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;
    }
}

✅Идеален за

• Малки масиви
• Почти сортирани данни
• Често се използва като fallback в хибридни алгоритми

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

Сложност	Стойност
Best Case	O(n) (вече сортиран)
Average Case	O(n²)
Worst Case	O(n²)
Space	O(1)
Stable	✅ Да
In-Place	✅ Да
Adaptive	✅ Да

---

Сравнителна Таблица на Простите Алгоритми

ℹ️Обобщение

Алгоритъм	Best	Average	Worst	Space	Stable	In-Place	Adaptive
Bubble	O(n)	O(n²)	O(n²)	O(1)	✅	✅	✅
Selection	O(n²)	O(n²)	O(n²)	O(1)	❌	✅	❌
Insertion	O(n)	O(n²)	O(n²)	O(1)	✅	✅	✅

---

5. Divide-and-Conquer Алгоритми

5.1 Merge Sort

ℹ️Концепция

Рекурсивно разделяне на масива, сортиране на двете половини, сливане (merge).

Как работи Merge Sort:

1. Divide: Разделяне на масива на две половини
2. Conquer: Рекурсивно сортиране на всяка половина
3. Combine: Сливане на сортираните половини

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];

    // Сливане на временните масиви обратно в arr
    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++;
    }
}

void mergeSort(std::vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

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

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

✅Предимства

• Гарантирана производителност: Винаги O(n log n)
• Стабилен: Запазва относителната подредба на равни елементи
• Предвидим: Няма worst-case деградация

⚠️Недостатък

Използва O(n) допълнителна памет за сливането - trade-off между време (по-добро) и памет (по-лошо) в сравнение с O(n²) алгоритмите.

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

Сложност	Стойност
Best Case	O(n log n)
Average Case	O(n log n)
Worst Case	O(n log n)
Space	O(n)
Stable	✅ Да
In-Place	❌ Не

---

5.2 Quicksort (Обзор)

ℹ️Концепция

Избор на pivot, разделяне на елементи по-малки/по-големи от pivot, рекурсивно сортиране на частите.

Как работи Quicksort:

1. Избор на pivot: Обикновено последният, първият, случаен или median-of-three
2. Partition: Пренареждане така че елементите < pivot са вляво, >= pivot са вдясно
3. Рекурсия: Сортиране на двете части

int partition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[high];  // избор на pivot
    int i = low - 1;        // индекс на по-малък елемент

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

void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

✅Защо е популярен?

• In-place: O(1) допълнителна памет (без рекурсията)
• Бърз на практика: Често по-бърз от merge sort поради по-добра cache locality
• Флексибилен: Различни стратегии за pivot

⚠️Внимание

Worst case е O(n²) при лош избор на pivot (рядко при добра стратегия).

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

Сложност	Стойност
Best Case	O(n log n)
Average Case	O(n log n)
Worst Case	O(n²)
Space	O(log n) рекурсия
Stable	❌ Не
In-Place	✅ Да

---

5.3 Heap Sort (Обзор)

ℹ️Концепция

Построяване на heap, многократно извличане на максимума, rebuilding на heap.

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

Сложност	Стойност
Best Case	O(n log n)
Average Case	O(n log n)
Worst Case	O(n log n)
Space	O(1)
Stable	❌ Не
In-Place	✅ Да

ℹ️Практика

Heap sort е по-бавен на практика от quicksort поради cache behavior, но гарантира O(n log n) и е in-place.

---

Merge Sort vs Quicksort: Практическо Сравнение

❌

Merge Sort

**Кога да използваме:** - Нужна е стабилност - Гарантирана производителност (без worst-case риск) - При linked lists (O(1) space merge) - External sorting (големи файлове) **Предимства:** - Винаги O(n log n) - Стабилен - Предвидим **Недостатъци:** - O(n) допълнителна памет - По-бавен на практика от quicksort

✅

Quicksort

**Кога да използваме:** - General-purpose сортиране - In-place изискване - Добра average-case производителност **Предимства:** - In-place (O(1) памет) - По-бърз на практика - Добра cache locality **Недостатъци:** - Worst case O(n²) (рядко) - Не е стабилен - Зависи от избора на pivot

---

6. Специализирани Non-Comparison Алгоритми

6.1 Counting Sort

ℹ️Концепция

Броене на срещанията на всяко цяло число, изчисляване на позиционна информация, извеждане на сортиран масив.

⚠️Приложимост

Само за целочислени масиви с малък диапазон (0..k). Ако k >> n, алгоритъмът става неефективен.

Имплементация:

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

    // Броене на срещанията
    for (int i = 0; i < n; i++)
        count[arr[i]]++;

    // Префиксни суми (позиции)
    for (int i = 1; i <= k; i++)
        count[i] += count[i - 1];

    // Построяване на output масив
    for (int i = n - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }

    // Копиране обратно
    for (int i = 0; i < n; i++)
        arr[i] = output[i];
}

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

Сложност	Стойност
Time	O(n + k)
Space	O(n + k)
Stable	✅ Да

---

6.2 Bucket Sort

ℹ️Концепция

Разпределяне на елементи в buckets, сортиране на всеки bucket (често с insertion sort), конкатенация.

Идеален за: Равномерно разпределени floats в [0, 1)

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

Сложност	Стойност
Average	O(n)
Worst	O(n²) (всички в един bucket)
Space	O(n)

---

6.3 Radix Sort

ℹ️Концепция

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

Идеален за: Големи списъци от цели числа или strings с фиксирана дължина на цифрите

Пример:

Сортиране на [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]

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

Сложност	Стойност
Time	O(d × n)
Space	O(n + k)
Stable	✅ Да

d = брой цифри, k = основа (обикновено 10)

---

7. Хибридни и Практически Подходи

Built-in C++ Sorting: std::sort

✅Препоръка

В продуктивен код винаги използвайте std::sort освен ако нямате специфична причина да не го правите!

Използване:

#include <algorithm>
#include <vector>

std::vector<int> v = {5, 2, 8, 1};
std::sort(v.begin(), v.end());  // Възходящо

// Низходящо
std::sort(v.begin(), v.end(), std::greater<int>());

ℹ️Какво е Introsort?

std::sort използва Introsort - хибрид от:

• Quicksort: Бърз в началото
• Heapsort: Превключва при дълбока рекурсия (лоши pivots) за O(n log n) worst-case
• Insertion sort: За малки масиви

Това осигурява и скорост на практика, и теоретична гаранция!

---

Lambda Expressions и Custom Comparators

Descending order:

std::sort(v.begin(), v.end(), [](int a, int b) {
    return a > b;  // Низходящо
});

Сортиране на structs/objects:

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

std::vector<Student> students = {
    {"Alice", 85},
    {"Bob", 92},
    {"Charlie", 78}
};

// Сортиране по оценка (низходящо)
std::sort(students.begin(), students.end(),
    [](const Student& a, const Student& b) {
        return a.grade > b.grade;
    }
);

Multi-key sorting:

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

---

8. Framework за Избор на Алгоритъм

ℹ️Как да решим кой алгоритъм да използваме?

Ситуация	Препоръчан Алгоритъм	Защо?
Малки масиви (n < 50)	Insertion sort	Прост, бърз (константите имат значение)
Large, general-purpose	Quicksort / Introsort	Бърз average, in-place
Worst-case гаранция	Merge sort	Винаги O(n log n), стабилен
Ограничена памет	Heap sort	In-place, O(n log n)
Известен диапазон на integers	Counting sort	Линейно време
Големи integers, фиксирани цифри	Radix sort	Линейно в броя цифри
Uniform float distribution	Bucket sort	Линейно очаквано време
Нужна стабилност	Merge sort, Counting sort	Запазват подредбата на равни
Почти сортирани данни	Insertion sort	Адаптивен, O(n) best case

💡Защо не винаги O(n log n)?

За малки n (< 50), простите O(n²) алгоритми често са по-бързи поради:

• По-малки константи
• По-добра cache locality
• Липса на overhead от рекурсия

Insertion sort често се използва в хибридни алгоритми като introsort за малки подмасиви!

---

9. Интерактивни Активности

Задача: Стъпка по стъпка проследете bubble sort на [3, 1, 4, 1, 5]

Цел: Разбиране на всяка размяна, всяко сравнение

Решение:

Начало: [3, 1, 4, 1, 5]
Pass 1: [1, 3, 1, 4, 5]  (swap 3,1; swap 3,1; swap 4,5)
Pass 2: [1, 1, 3, 4, 5]  (swap 3,1)
Pass 3: [1, 1, 3, 4, 5]  (без swaps - готово!)

Въпрос: Защо insertion sort е по-бърз от bubble или selection sort за почти сортирани данни?

Отговор: Insertion sort работи в O(n) когато е почти сортиран, защото много малко shifts/swaps са нужни; bubble/selection винаги правят n² сравнения.

Сценарий: Изберете алгоритъм за сортиране за e-commerce сайт с милиони продукти, където често се добавят нови продукти. Обосновете избора си.

Възможни отговори:

• Merge sort за стабилност и гарантирана производителност
• Quicksort/Introsort за бързина на практика
• Hybrid подход според размера на данните

Задача: Напишете и измерете времето на вашите insertion, bubble и merge sorts на различни размери на входа. Визуализирайте разликата в производителността!

Примерен код:

#include <chrono>

auto start = std::chrono::high_resolution_clock::now();
// ... вашият алгоритъм ...
auto end = std::chrono::high_resolution_clock::now();

auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
std::cout << "Time: " << duration.count() << " ms\n";

---

10. Формативно Оценяване

Въпрос: Обяснете този алгоритъм: "Намира минимума и го премества в сортираната част"

Отговор: Selection sort, O(n²)

Сценарий: "Имате 10,000 случайни цели числа за сортиране." Препоръчан алгоритъм? Защо?

Очакван отговор: Merge sort или quicksort - O(n log n) време, много по-бърз за големи данни.

Задача: Напишете рекурсивен merge sort. Какъв е вашият base case? Как правите merge?

Проверка: Могат ли студентите да управляват рекурсията, правилно да сливат без загуба на данни?

---

11. Обобщение и Ключови Извлечения

🎯 Няма Универсално Решение

• Прости алгоритми са най-добри за малки или почти сортирани масиви
• За large, general-purpose: quicksort/introsort
• За гарантирана стабилност и производителност: merge sort

📊 Мислете Отвъд Big-O

• Реални размери на данни
• Cache behavior
• Константни фактори
• Винаги профилирайте и измервайте!

⚡ Non-Comparison за Известни Диапазони

• Counting, radix и bucket sorts използват специални свойства на входа
• Постигат O(n) когато е приложимо
• Ограничени до специфични типове данни

🔧 Хибридни Алгоритми Властват

• std::sort (introsort) комбинира най-доброто теоретично и практическо
• Quicksort → Heapsort при лоши pivots
• Insertion sort за малки подмасиви

✅Сортирането е Gateway

Принципите, научени тук (divide-and-conquer, trade-offs в производителността, емпирична валидация), се прилагат във всички области на алгоритмичното решаване на проблеми!

---

12. Препоръчани Следващи Стъпки

1. Практикувайте Coding: Имплементирайте поне три алгоритъма от нулата
2. Проследете Ръчно: Мануално проследете всеки алгоритъм на малки масиви
3. Профилирайте на Големи Данни: Benchmark на вашите имплементации срещу std::sort
4. Експериментирайте с Custom Comparators: Използвайте lambdas за сортиране на structs и комплексни обекти
5. Рефлектирайте върху Избора: За нови данни питайте: Какво знам? Какво ми трябва? Кой алгоритъм пасва?

---

Допълнителни Ресурси

Онлайн Туториали

• GeeksforGeeks - Sorting Algorithms - Comprehensive coverage of all sorting algorithms
• TutorialsPoint - Data Structures & Algorithms - Sorting - Tutorial with examples
• CP-Algorithms - Sorting - Advanced sorting techniques

Визуализация и Примери

• VisuAlgo - Sorting - Интерактивна визуализация на всички sorting алгоритми
• Sorting Algorithms Animations - Animated comparison of algorithms
• Algorithm Visualizer - Interactive algorithm visualization tool

Видео Лекции

• MIT OpenCourseWare - Introduction to Algorithms - Lectures 3-5 cover sorting
• Abdul Bari - Sorting Algorithms - Excellent video series on YouTube
• CS50 - Sorting - Harvard's CS50 sorting lecture

Практически Задачи

• LeetCode - Sorting Tag - Practice problems on sorting
• HackerRank - Sorting - Sorting challenges
• CodeForces - Sortings - Competitive programming problems

Книги и Статии

• "Introduction to Algorithms" (CLRS) - Chapters 2, 6, 7, 8 - The definitive reference
• "Algorithms" by Robert Sedgewick - Practical implementations and analysis
• "The Algorithm Design Manual" by Steven Skiena - Real-world algorithm selection guide

C++ Reference

• cppreference.com - std::sort - Official C++ sorting documentation
• C++ STL Algorithms - Complete STL algorithm reference

---

Край на Лекцията