Как работает алгоритм быстрой сортировки?

Алгоритм быстрой сортировки (QuickSort) — это рекурсивный алгоритм, который работает по принципу "разделяй и властвуй".

1. Выбор опорного элемента (pivot): Выбирается один элемент из массива. Способов выбора несколько: первый элемент, последний, медиана из трех, случайный.
2. Разбиение (partition): Элементы массива переставляются так, чтобы все элементы меньше опорного оказались перед ним, а все элементы больше — после него. Элементы, равные опорному, могут быть в любой из двух частей. После этого разбиения опорный элемент занимает свое окончательное отсортированное место.
3. Рекурсивная сортировка подмассивов: Алгоритм рекурсивно применяется к подмассиву элементов меньше опорного и к подмассиву элементов больше опорного.

Базовым случаем рекурсии является массив из одного или нуля элементов, который уже считается отсортированным.

Псевдокод:

quicksort(arr, low, high)
  if low < high
    pivot_index = partition(arr, low, high)
    quicksort(arr, low, pivot_index - 1)
    quicksort(arr, pivot_index + 1, high)

Функция разбиения (пример):

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

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

Сложность:

• Средняя: Пространственная O(log n) (из-за рекурсивных вызовов), временная O(n log n).
• Худшая: Пространственная O(n) (при несбалансированном разбиении), временная O(n^2) (когда каждый раз выбирается минимальный или максимальный элемент в качестве опорного). Этого можно избежать с помощью хорошего выбора опорного элемента.