Сортировка Хоара (Quick Sort): быстрая сортировка

Также упоминается как: quicksort, qsort (функция стандартной библиотеки C), алгоритм Хоара, метод Хоара

Идея метода сортировки

Быстрая сортировка Хоара является одним из самых популярных алгоритмов сортировки благодаря очень низкой константе (числу операций процессора) при среднем времени работы O(N log N).

• Шаг 1. Выбираем опорный элемент (pivot). В классической, самой простой реализации это просто последний элемент подмассива.
• Шаг 2 (Partition - Разбиение). Проходим по массиву: все элементы, которые меньше или равны pivot, отправляем влево, а те, что больше - вправо.
• Шаг 3. В результате разбиения опорный элемент занимает свое абсолютно точное, финальное местоположение в массиве.
• Шаг 4. Рекурсивно применяем этот же алгоритм к левой и правой частям от опорного элемента.

Интерактивный пример наглядно иллюстрирует, как сортировка Хоара выбирает опорный элемент и раскидывает числа на две группы.

Уязвимость (Худший случай O(N²))

Несмотря на название, "Быстрая" сортировка скрывает в себе серьезную уязвимость. Если в качестве опорного элемента всегда брать крайний элемент, а на вход программе подать уже отсортированный массив (например, [1, 2, 3, 4, 5, 6, 7]), то алгоритм сломается:

• Pivot равен 7. Слева от него оказываются все 6 элементов, справа - 0.
• На следующем шаге Pivot = 6. Слева - 5 элементов, справа - 0.

Вместо красивого деления массива пополам (что дает глубину рекурсии log N), мы будем откусывать от массива по 1 элементу. Алгоритм деградирует до O(N²), а глубина рекурсии достигнет N.

Две схемы разбиения: Ломуто и Хоара

В быстрой сортировке этап Partition (Разбиение) можно реализовать двумя классическими способами. Они отличаются тем, как выбирается опорный элемент и как элементы переносятся между частями.

• Схема Ломуто (Lomuto): Простая и понятная. Опорным берется последний элемент, а проход идет одним индексом слева направо: каждый элемент, не больший опорного, переносится в левую зону. В конце опорный встает ровно на свое финальное место, и функция возвращает его индекс. Именно она разобрана в коде ниже. Платит за простоту большим числом обменов и хуже ведет себя на массивах из одинаковых элементов.
• Схема Хоара (Hoare): Оригинальная схема Тони Хоара (1961). Опорным берется левый (или средний) элемент, а к массиву идут сразу два индекса - слева и справа - навстречу друг другу. Они находят пару элементов, стоящих не на своей стороне, и меняют их местами; когда указатели встречаются, часть разбита. Опорный при этом не обязан встать на финальное место, зато обменов получается примерно втрое меньше. Именно эту схему показывает тренажер выше в уроке.

Реализация на языке C (Схема разбиения Ломуто)

void Swap(int* a, int* b) { int t = *a; *a = *b; *b = t; }

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

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

// Сама рекурсивная функция
void QuickSort(int arr[], int low, int high) {
    if (low < high) {
        // Получаем индекс разделения
        int pi = Partition(arr, low, high);

        // Рекурсивно сортируем элементы до и после опорного
        QuickSort(arr, low, pi - 1);
        QuickSort(arr, pi + 1, high);
    }
}