Skip to content

🔍 Алгоритми за Сортиране: Пълно Ръководство

Сортирането е фундаментална операция в информатиката, която подрежда елементите на списък в определен ред (най-често възходящ или низходящ). Изборът на правилния алгоритъм зависи от размера на данните (\(N\)), ограниченията за памет и спецификите на елементите.

1. Прости алгоритми: \(O(N^2)\)

Тези алгоритми са лесни за имплементация, но неефективни за големи масиви (\(N > 2000\)).

1.1. Метод на мехурчето (Bubble Sort)

Многократно обхожда масива, като разменя съседни елементи, ако са в грешен ред. Най-тежкият елемент "изплува" като мехурче накрая. 

void bubbleSort(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]) {
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break; // Оптимизация
    }
}

1.2. Сортиране чрез вмъкване (Insertion Sort)

Изгражда сортирания масив елемент по елемент. Взима следващия и го "вмъква" на правилното място сред вече сортираните. * Предимство: Изключително бърз (\(O(N)\)) за почти сортирани данни. * Употреба: Често се използва като базов случай в по-сложни алгоритми (напр. Timsort, който е в основата на сортирането в Python и Java, използва Insertion Sort за малки парчета).

2. Ефективни алгоритми: \(O(N \log N)\)

Задължителни за състезания, където \(N\) достига \(10^5\) или \(10^6\).

2.1. Сортиране чрез сливане (Merge Sort)

Класически пример за стратегията "Разделяй и владей" (Divide and Conquer). 1. Разделяне: Масивът се дели на две половини. 2. Владеене: Всяка половина се сортира рекурсивно. 3. Сливане: Двете сортирани половини се обединяват (merge) в един сортиран масив.

  • Стабилност: Да (запазва реда на равните елементи).
  • Памет: Изисква \(O(N)\) допълнителна памет.
void merge(vector<int>& arr, int l, int m, int r) {
    vector<int> temp;
    int i = l, j = m + 1;
    while (i <= m && j <= r) {
        if (arr[i] <= arr[j]) temp.push_back(arr[i++]);
        else temp.push_back(arr[j++]);
    }
    while (i <= m) temp.push_back(arr[i++]);
    while (j <= r) temp.push_back(arr[j++]);
    for (int k = 0; k < temp.size(); k++) arr[l + k] = temp[k];
}

void mergeSort(vector<int>& arr, int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

2.2. Бързо сортиране (Quick Sort)

Също използва "Разделяй и владей", но разделянето става чрез Pivot (опорен елемент). Всички по-малки от пивота отиват вляво, а по-големите – вдясно. * Бързина: В практиката е по-бърз от Merge Sort, защото работи "in-place" (без допълнителна памет) и има добра кеш-локалност. * Най-лош случай: \(O(N^2)\), ако пивотът е лошо избран (напр. сортиран масив). * std::sort в C++ използва хибриден вариант (Introsort: QuickSort + HeapSort), за да гарантира \(O(N \log N)\).

3. Линейни сортировки: \(O(N)\)

Възможни са само ако знаем нещо повече за данните (напр. че са цели числа в малък диапазон).

3.1. Counting Sort (Сортиране чрез броене)

Ако числата са в интервала \([0, K]\): 1. Създаваме масив cnt[K+1] с нули. 2. За всяко число x от входа, увеличаваме cnt[x]. 3. Извеждаме индекса i точно cnt[i] пъти. Сложност: \(O(N + K)\).

3.2. Radix Sort (Поразредно сортиране)

Сортира числата цифра по цифра (обикновено от последната към първата), използвайки стабилен Counting Sort за всяка позиция. Сложност: \(O(D \cdot (N+K))\), където \(D\) е броят цифри.

4. Използване на std::sort в C++

В 99% от случаите в състезания трябва да използвате вградения sort.

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

using namespace std;

struct Student {
    string name;
    int score;
};

// Сравнителна функция (Comparator)
bool compareStudents(const Student& a, const Student& b) {
    if (a.score != b.score)
        return a.score > b.score; // Низходящо по точки
    return a.name < b.name;       // Възходящо по име при равни точки
}

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

    // Стандартно сортиране (възходящо)
    sort(v.begin(), v.end()); 

    // Низходящо с ламбда функция
    sort(v.begin(), v.end(), [](int a, int b) {
        return a > b; 
    });

    vector<Student> students = {{"Ivan", 90}, {"Ani", 95}, {"Bobi", 90}};
    sort(students.begin(), students.end(), compareStudents);

    return 0;
}

std::stable_sort

Ако искате да запазите реда на елементите, които са равни според критерия за сравнение, използвайте stable_sort. Той обикновено е базиран на Merge Sort и е малко по-бавен, но понякога е необходим.

5. Практически съвети и често срещани грешки

5.1. Проблеми със сравнителната функция

Една от най-честите грешки при използване на sort е написване на невалидна функция за сравнение. Тя трябва да: * Бъде транзитивна: Ако \(A < B\) и \(B < C\), то \(A < C\). * Бъде антисиметрична: Ако \(A < B\), то НЕ \(B < A\). * Ако \(A\) НЕ е по-малко от \(B\) и \(B\) НЕ е по-малко от \(A\), то са равни.

Грешна функция може да доведе до Segmentation Fault или непредсказуеми резултати.

5.2. Сортиране на структури с operator<

Вместо да подавате функция, можете да дефинирате operator< за вашата структура: 

struct Point {
    int x, y;
    bool operator<(const Point& other) const {
        if (x != other.x) return x < other.x;
        return y < other.y;
    }
};

vector<Point> points = {{3,5}, {1,2}, {3,1}};
sort(points.begin(), points.end()); // Вече работи директно

5.3. Сортиране на част от масива

Можете да сортирате само определен участък: 

vector<int> arr = {5, 2, 9, 1, 5, 6};
sort(arr.begin() + 1, arr.begin() + 4); // Сортира индекси [1, 4)
// Резултат: {5, 1, 2, 9, 5, 6}

5.4. Частично сортиране (partial_sort)

Ако ви трябват само първите \(K\) най-малки елемента, partial_sort е по-бърз от пълното сортиране: 

vector<int> v = {5, 1, 9, 3, 7, 2};
partial_sort(v.begin(), v.begin() + 3, v.end());
// Първите 3 са сортирани: {1, 2, 3, ...}
Сложност: \(O(N \log K)\) вместо \(O(N \log N)\).

6. Задачи за упражнение

  1. CSES Distinct Numbers: Използвайте сортиране за намиране на уникални елементи.
  2. Codeforces 339D: Изисква сортиране с персонализирана функция.
  3. AtCoder ABC128C: Комбинация на сортиране и структури.

🏁 Заключение

Изборът на правилен алгоритъм зависи от контекста: * \(N \le 2000\): Bubble Sort или Insertion Sort са достатъчни (ако времето позволява). * \(N \le 10^6\): Използвайте std::sort (Introsort). * Стабилност е критична: std::stable_sort. * Специфични ограничения: Counting Sort или Radix Sort.

Запомнете: в 99% от случаите в състезания просто пишете sort(arr.begin(), arr.end()) – не изобретявайте колелото наново!