Всем привет! Подтолкнуло написать меня эту статью мой непосредственный интерес к алгоритмам и решению задач на leetcode, каждый раз, используя стандартную сортировку из STL std::sort, я знал, что ее сложность O(n*log(n)), но как она реализована внутри не доходили руки разобраться, в добавок мне стало интересно, какие есть другие виды сортировок, кроме самых простых, с которыми каждый знакомится в начале своего пути.

Я решил это исправить! И описать все виды сортировок, с которыми мне так или иначе приходилось встречать во время выполнения своих тасков или решению задач на leet.

Начнем с того, что разберемся, какие виды сортировок вообще есть и разобьем их на условные простые/продвинутые/для специальных случаев, а также разберемся, что использует std::sort у себя под капотом.

Начнем!

std::sort — это стандартная функция сортировки, находится в <algorithm>. Она использует комбинацию QuickSort, HeapSort, и InsertionSort для достижения высокой производительности.

• Алгоритм под капотом:

• Используется модифицированный introsort (Introspective Sort).

Это гибридный алгоритм, который:

1. Начинает с QuickSort.

2. Если глубина рекурсии становится слишком большой (может указывать на худший случай), переключается на HeapSort.
   
   *Для небольших подмассивов применяется InsertionSort, так как он эффективен для малых объёмов данных.

3. По итогу получаем сложность O(n log n) в среднем случае и гарантированную устойчивость даже для худших случаев.

Идем дальше!

• Простые алгоритмы (Bubble Sort, Insertion Sort, Selection Sort).

• Продвинутые алгоритмы (Merge Sort, Quick Sort, Heap Sort).

• Алгоритмы для специальных случаев (Counting Sort, Radix Sort, Bucket Sort).

Рассмотрим каждый из них и варианты реализации:

1. Простые алгоритмы сортировки

Bubble Sort (Пузырьковая сортировка)

Алгоритм сравнивает соседние элементы и меняет их местами, если правый элемент больше левого. Повторяется до тех пор, пока массив не будет отсортирован.
Сложность: O(n²)

template<typename T>
void BubbleSort(std::vector<T>& vec)
{
    bool swapped;
    for (size_t i = 0; i < vec.size(); ++i)
    {
        swapped = false;
        for (size_t j = 0; j < vec.size() - i - 1; ++j)
        {
            if (vec[j] > vec[j + 1]) {
                std::swap(vec[j], vec[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) {
            break;
        }
    }
}

Меньший элемент перемещается “вверх”, как пузырёк.

Insertion Sort (Сортировка вставками)

Элементы из неотсортированной части массива постепенно вставляются в правильную позицию отсортированной части.
Сложность: O(n²)

template<typename T>
void insertionSort(vector<T>& vec) 
{ 
    for (int32_t i = 1; i < vec.size(); ++i)
    { 
        T key = vec[i];
        int32_t j = i - 1; 
        while (j >= 0 && vec[j] > key)
        {
            vec[j + 1] = vec[j]; --j;
        } 
        vec[j + 1] = key; }
}

Идеально подходит для небольших массивов или почти отсортированных данных.

Selection Sort (Сортировка выбором)

На каждом шаге выбирается минимальный элемент из оставшейся части массива и перемещается в начало.
Сложность: O(n²)

template<typename T>
void selectionSort(vector<T>& vec)
{
    for (auto it = vec.begin(); it < vec.end()-1; ++it)
    {
        auto minIt = it;
        for (auto it2 = it + 1; it2 <vec.end(); ++it2)
        {
            if ((*it2) <(*minIt)) {
                minIt = it2;
            }
        }
        swap((*it), *(minIt));
    }
}

Простой алгоритм, но неэффективный для больших данных.

Так, на этом этапе я думаю многие вспомнили себя и как они первый раз познакомились с алгоритмами, дальше будут примеры, которые могли вам не встречаться, но они будут асимптотически быстрее и интереснее!

2. Продвинутые алгоритмы сортировки

Merge Sort (Сортировка слиянием)

Идея заключается в том, что вы делите массив на две части, сортирует их рекурсивно и затем сливает в единый отсортированный массив.

Сложность: O(n log n) - уже интереснее, чем O(n²)!

template <typename T>
void merge(vector<T>& vec, uint64_t left, uint64_t mid, uint64_t right) {
    vector<T> temp;
    uint64_t i = left;
    uint64_t j = mid + 1;

    while (i <= mid && j <= right) {
        if (vec[i] <= vec[j]) {
            temp.push_back(vec[i++]);
        }
        else {
            temp.push_back(vec[j++]);
        }
    }

    while (i <= mid) temp.push_back(vec[i++]);
    while (j <= right) temp.push_back(vec[j++]);

    for (uint32_t k = 0; k < temp.size(); ++k) {
        vec[left + k] = temp[k];
    }
}
template<typename T>
void mergeSort(vector<T>& vec, uint64_t left, uint64_t right) {
    if (left >= right) return;

    uint64_t mid = left + (right - left) / 2;
    mergeSort<T>(vec, left, mid);
    mergeSort<T>(vec, mid + 1, right);
    merge<T>(vec, left, mid, right);
}

Quick Sort (Быстрая сортировка)

Выбирается опорный элемент (pivot), элементы меньшие pivot идут влево, больше — вправо. Затем процесс повторяется рекурсивно.

Сложность: Средняя O(n log n), худшая O(n²)

template<typename T>
int64_t partition(vector<T>& vec, int64_t low, int64_t high) {
    T pivot = vec[high];
    int64_t i = low - 1;

    for (int64_t j = low; j < high; ++j) {
        if (vec[j] < pivot) {
            swap(vec[++i], vec[j]);
        }
    }
    swap(vec[i + 1], vec[high]);
    return i + 1;
}
template<typename T>
void quickSort(vector<T>& vec, int64_t low, int64_t high) {
    if (low < high) {
        int64_t pi = partition(vec, low, high);
        quickSort(vec, low, pi - 1);
        quickSort(vec, pi + 1, high);
    }
}

Heap Sort (Сортировка кучей)

Очень интересный вариант сортировки, потому что строится на heap(кучи), представляющую собой бинарное дерево. Алгоритм сначала строит кучу из массивов, а затем извлекает элементы из кучи по порядку (по возрастанию или убыванию).
Сложность: O(n log n) - при любом случае, так еще и память - O(1) in-place)

Привел описание алгоритма в самом коде

template <typename T>
void heapify(std::vector<T>& vec, int32_t n, int32_t i) {
    int32_t largest = i; // Изначально считаем корневой элемент наибольшим
    int32_t left = 2 * i + 1; // Левый дочерний узел
    int32_t right = 2 * i + 2; // Правый дочерний узел
    // Если левый дочерний узел больше корня
    if (left < n && vec[left] > vec[largest]) {
        largest = left;
    }
    // Если правый дочерний узел больше корня
    if (right < n && vec[right] > vec[largest]) {
        largest = right;
    }
    // Если наибольший элемент — не корень
    if (largest != i) {
        std::swap(vec[i], vec[largest]);

        // Рекурсивно применяем heapify к дочернему узлу
        heapify(vec, n, largest);
    }
}
template <typename T>
void heapSort(std::vector<T>& vec) {
    int32_t n = vec.size();
    // Построение кучи (перегруппировка массива)
    for (int32_t i = n / 2 - 1; i >= 0; --i) {
        heapify(vec, n, i);
    }
    // Извлечение элементов из кучи
    for (int32_t i = n - 1; i > 0; --i) {
        // Перемещаем текущий корень (наибольший элемент) в конец массива
        std::swap(vec[0], vec[i]);
        // Вызываем heapify для уменьшенной кучи
        heapify(vec, i, 0);
    }
}

3. Алгоритмы для специальных случаев

Почему я назвал их специальные? Потому,что эти алгоритмы подходят для задач с определёнными условиями, например, сортировка целых чисел в ограниченном диапазоне, объектов с ключами фиксированного размера или данных с определённой структурой и другое.

Counting Sort (Сортировка подсчётом)

Counting Sort подходит для сортировки целых чисел в небольшом диапазоне значений. Вместо сравнения элементов используется массив для подсчёта количества вхождений каждого значения.

Сложность: O(n + k), где n — количество элементов, а k — диапазон значений.
Память: O(k).
Особенности:

• Эффективна только для целых чисел в ограниченном диапазоне.
• Не in-place, так как требуется дополнительная память.

template <typename T>
vector<T> countingSort(const vector<T>& vec) {
    if (vec.empty()) return {}; 

    // max element
    size_t size = vec.size();
    T max_elem = *max_element(vec.begin(), vec.end());

    // Создаём вектор для подсчёта частоты элементов
    vector<size_t> count_vec(max_elem + 1, 0);
  
    for (size_t i = 0; i < size; i++)
    {
        count_vec[vec[i]]++;
    }
  
    // Преобразуем вектор подсчёта в кумулятивную сумму
    for (size_t i = 1; i < count_vec.size(); i++)
    {
        count_vec[i] += count_vec[i - 1];
    }
  
    // Формируем результирующий массив
    vector<T> result(size);
    for (int i = size - 1; i >= 0; i--)
    {
        result[count_vec[vec[i]] - 1] = vec[i];
        count_vec[vec[i]]--;
    }
    return result;
}

Если входная коллекция будет очень большой, то алгоритм теряет весь смысл, поэтому подчеркну еще раз - Эффективна только для целых чисел в ограниченном диапазоне!

Radix Sort (Поразрядная сортировка)

Radix Sort сортирует числа по разрядам, начиная с младшего. В качестве подалгоритма обычно используется Counting Sort, чтобы обеспечить устойчивость.
Сложность: O(n * d), где n — количество элементов, а d — количество разрядов в числе.
Память: O(n + k), где k — диапазон цифр (обычно 10 для десятичной системы).
Особенности:
• Подходит для чисел (целых или с плавающей точкой) или строк фиксированной длины.
• Требует дополнительных вычислений для обработки отрицательных чисел.

template <typename T>
void countSort(vector<T>& vec, size_t size, T exp) {
    vector<T> result(size);           
    vector<size_t> count(10, 0);  
  
    for (size_t i = 0; i < size; i++)
    {
        count[(static_cast<int>(vec[i] / exp) % 10)]++;
    }
    // Преобразование count в кумулятивную сумму
    for (size_t i = 1; i < 10; i++)
    {
        count[i] += count[i - 1];
    }
    // Формирование результата, начиная с конца
    for (int i = size - 1; i >= 0; i--)
    {
        int digit = static_cast<int>(vec[i] / exp) % 10;
        result[count[digit] - 1] = vec[i];
        count[digit]--;
    }
    // Копирование результата обратно
    for (size_t i = 0; i < size; i++)
    {
        vec[i] = result[i];
    }
}

template <typename T>
void radixSort(vector<T>& vec)
{
    if (vec.empty()) return;

    // max element
    T maxElement = *max_element(vec.begin(), vec.end());

    // Сортируем по каждому разряду
    for (T exp = 1; maxElement / exp > 0; exp *= 10)
    {
        countSort(vec, vec.size(), exp);
    }
}

Bucket Sort (Сортировка корзинами)

Bucket Sort делит элементы на несколько корзин (buckets), сортирует каждую корзину отдельно (обычно с помощью другой сортировки, например, Insertion Sort), а затем объединяет их.

Сложность:
• Лучший случай: O(n) (равномерное распределение элементов по корзинам).
• Худший случай: O(n²) (если все элементы попадают в одну корзину).
Память: O(n + k), где k — количество корзин.

Особенности:
• Эффективен для равномерно распределённых данных.
• Можно используется для чисел с плавающей точкой.

template <typename T>
void bucketSort(vector<T>& arr) {
    if (arr.empty()) return;

    // Определяем максимальный и минимальный элемент
    T minValue = *min_element(arr.begin(), arr.end());
    T maxValue = *max_element(arr.begin(), arr.end());

    // Вычисляем кол-во корзин
    size_t bucketCount = arr.size();
    vector<vector<T>> buckets(bucketCount);

    // Распределяем элементы по bucket-ам
    for (const auto& num : arr) {
        size_t bucketIndex = static_cast<size_t>((num - minValue) / (maxValue - minValue + 1) * bucketCount);
        buckets[bucketIndex].push_back(num);
    }

    size_t index = 0;
    for (auto& bucket : buckets) {
        sort(bucket.begin(), bucket.end()); // Сортируем корзину 
        for (const auto& num : bucket) {
            arr[index++] = num; // Переносим обратно в оригинальный массив
        }
    }
}

Итог

Внизу приведу таблицу с характеристиками каждого из алгоритмов. Надеюсь, тем, кто не был близко знаком с алгоритмами, стало понятнее и нагляднее, какие варианты сортировок существуют и как они реализуются. Не гонюсь за лучшей реализацией такого, или иного алгоритма, но как по мне, варианты написания, которые я привел, не плохие. Есть еще множество других вариантов сортировок, но как по мне, я привел самые распространенные.

Вот и всё, всем удачи!

P.S: Устойчивость алгоритма означает, что порядок равных элементов в исходном массиве сохраняется в отсортированном массиве.

Жуков Матвей НИУ МЭИ ИВТИ/Кафедра управления и интеллектуальных технологий

С++ Разработчик в Servicepipe.