Что такое быстрая сортировка?

Что такое быстрая сортировка (Quicksort)

Quicksort — это один из самых важных и широко используемых алгоритмов сортировки. Он основан на парадигме divide-and-conquer и в среднем значительно быстрее других методов сортировки.

Основная идея

Алгоритм работает по принципу:

1. Выбрать pivot (опорный элемент)
2. Разделить массив на две части: элементы меньше pivot и элементы больше pivot
3. Рекурсивно сортировать обе части
4. Объединить результаты

Отличие от merge sort: нет необходимости объединять — разделение само создаёт порядок.

Реализация

Классический вариант с Lomuto partition:

int partition(std::vector<int>& arr, int low, int high) {
    // Выбираем последний элемент как pivot
    int pivot = arr[high];
    
    // i указывает на позицию, где должны быть элементы < 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;  // Индекс pivot'а в отсортированном положении
}

void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        // Разделяем и получаем индекс pivot'а
        int pi = partition(arr, low, high);
        
        // Рекурсивно сортируем левую часть
        quickSort(arr, low, pi - 1);
        
        // Рекурсивно сортируем правую часть
        quickSort(arr, pi + 1, high);
    }
}

Более эффективный вариант с Hoare partition:

int hoare_partition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[low];
    int i = low - 1;
    int j = high + 1;
    
    while (true) {
        // Ищем элемент слева, который >= pivot
        do {
            i++;
        } while (arr[i] < pivot);
        
        // Ищем элемент справа, который <= pivot
        do {
            j--;
        } while (arr[j] > pivot);
        
        if (i >= j) return j;
        
        std::swap(arr[i], arr[j]);
    }
}

Процесс работы (пример)

Исходный массив: [38, 27, 43, 3, 9, 82, 10]
Выбираем pivot = 10

После partition:
[3, 9, 10, 27, 43, 38, 82]
      ↑
    pivot

Левая часть:  [3, 9]     → quickSort
Правая часть: [27, 43, 38, 82] → quickSort

Итоговый результат: [3, 9, 10, 27, 38, 43, 82]

Сложность

Worst case: когда массив уже отсортирован и выбираем первый элемент как pivot!

Оптимизации

1. Выбор лучшего pivot:

int median_of_three(std::vector<int>& arr, int low, int high) {
    int mid = (low + high) / 2;
    
    if (arr[low] > arr[mid]) std::swap(arr[low], arr[mid]);
    if (arr[low] > arr[high]) std::swap(arr[low], arr[high]);
    if (arr[mid] > arr[high]) std::swap(arr[mid], arr[high]);
    
    std::swap(arr[mid], arr[high]);  // Переместим медиану в конец
    return arr[high];
}

2. Hybrid approach (IntroSort):

Проблема: O(n²) worst case. Решение:

void introsort(std::vector<int>& arr, int low, int high, int depth_limit) {
    while (high > low) {
        if (depth_limit == 0) {
            // Слишком глубокая рекурсия → переходим на heap sort
            std::make_heap(arr.begin() + low, arr.begin() + high + 1);
            std::sort_heap(arr.begin() + low, arr.begin() + high + 1);
            return;
        }
        
        int pi = partition(arr, low, high);
        
        // Рекурсивно сортируем меньшую часть
        if (pi - low < high - pi) {
            introsort(arr, low, pi - 1, depth_limit - 1);
            low = pi + 1;
        } else {
            introsort(arr, pi + 1, high, depth_limit - 1);
            high = pi - 1;
        }
        
        depth_limit--;
    }
}

Это гарантирует O(n log n) в worst case!

Особенности

Преимущества:

• In-place сортировка — O(log n) дополнительной памяти
• Cache-friendly — хорошо работает с памятью процессора
• Быстрая на практике — часто быстрее O(n log n) алгоритмов
• Parallelizable — можно параллелить на multi-core

Недостатки:

• Unstable sort — не сохраняет относительный порядок равных элементов
• Worst case O(n²) — может быть медленным на определённых входах
• Рекурсивна — может вызвать stack overflow на очень больших данных

Использование в C++

// std::sort в C++ обычно использует IntroSort (GCC, Clang)
#include <algorithm>

std::vector<int> arr = {38, 27, 43, 3, 9, 82, 10};
std::sort(arr.begin(), arr.end());  // O(n log n) гарантировано

// Сортировка с компаратором
std::sort(arr.begin(), arr.end(), [](int a, int b) { return a > b; });

Заключение

Quicksort — фундаментальный алгоритм в computer science. Он служит основой для std::sort в C++ STL и остаётся одним из самых практичных алгоритмов сортировки благодаря отличной cache locality и low memory overhead.