Что такое алгоритм быстрой сортировки (QuickSort)?

QuickSort — это эффективный алгоритм сортировки сравнением, работающий по принципу «разделяй и властвуй». Его ключевая идея — выбрать опорный элемент (pivot) и переупорядочить массив так, чтобы все элементы меньше pivot оказались слева от него, а все большие или равные — справа (процедура partition). Затем алгоритм рекурсивно применяется к двум полученным подмассивам.

Реализация на C++ (итеративная с использованием стека для избежания глубокой рекурсии):

#include <iostream>
#include <stack>
#include <utility>

// Функция разделения (partition) по схеме Ломуто
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // Выбираем последний элемент как опорный
    int i = low - 1; // Индекс меньшего элемента

    for (int j = low; j < high; ++j) {
        // Если текущий элемент меньше или равен опорному
        if (arr[j] <= pivot) {
            ++i;
            std::swap(arr[i], arr[j]);
        }
    }
    // Помещаем pivot на правильную позицию
    std::swap(arr[i + 1], arr[high]);
    return i + 1; // Возвращаем индекс pivot
}

// Итеративная QuickSort (использует явный стек вместо рекурсии)
void quickSortIterative(int arr[], int low, int high) {
    std::stack<std::pair<int, int>> stack;
    stack.push({low, high});

    while (!stack.empty()) {
        auto [l, h] = stack.top();
        stack.pop();

        if (l >= h) continue; // Базовый случай рекурсии

        int p = partition(arr, l, h); // Индекс разбиения

        // Кладем в стек диапазоны для сортировки, начиная с меньшего
        // Это оптимизация, ограничивающая глубину стека.
        if (p - 1 > l) {
            stack.push({l, p - 1});
        }
        if (p + 1 < h) {
            stack.push({p + 1, h});
        }
    }
}

int main() {
    int data[] = {10, 7, 8, 9, 1, 5, 3, 12, 4};
    int n = sizeof(data) / sizeof(data[0]);

    quickSortIterative(data, 0, n - 1);

    std::cout << "Sorted array: ";
    for (int i = 0; i < n; ++i) {
        std::cout << data[i] << " ";
    }
    std::cout << std::endl;
    return 0;
}

Характеристики и важные детали:

• Средняя временная сложность: O(n log n). Это делает QuickSort одним из самых быстрых алгоритмов на практике для сортировки массивов в памяти.
• Худший случай O(n²) возникает при неудачном выборе pivot (например, всегда минимальный или максимальный элемент) на уже отсортированном или почти отсортированном массиве. Способы борьбы:
  1. Выбор медианы трех (первого, среднего и последнего элементов) как pivot.
  2. Случайный выбор pivot (std::swap(arr[high], arr[low + rand() % (high - low + 1)]);).
• Пространственная сложность: В среднем O(log n) для стека вызовов (или явного стека, как в примере). В худшем случае O(n).
• Неустойчивость: QuickSort не сохраняет относительный порядок равных элементов.
• In-place: Алгоритм сортирует данные в исходном массиве, используя лишь небольшой объем дополнительной памяти.

Когда использовать: QuickSort — отличный выбор для сортировки больших массивов примитивных типов в памяти, где важна скорость. Для сортировки связанных списков или в ситуациях, где требуется стабильность, лучше подходят MergeSort или TimSort.