Quick Sort

Проблема

Сортировка слиянием гарантирует O(n log n), но платит за это O(n) дополнительной памяти на каждом слиянии. Нужен алгоритм с той же асимптотикой в среднем случае, но сортирующий на месте - то есть почти не потребляющий дополнительной памяти, что критично для больших массивов в памяти с ограниченным объёмом.

Решение

Выбирается опорный элемент (pivot) - например, последний элемент подмассива. Массив переставляется («партиционируется») так, что все элементы меньше опорного оказываются слева от него, а все больше - справа; сам опорный элемент встаёт на своё окончательное отсортированное место. Затем алгоритм рекурсивно применяется к левой и правой частям отдельно, до подмассивов длины 0 или 1.

Как это работает

Разберём партиционирование на конкретном примере: arr = [8, 2, 5, 3, 9, 4, 7], low = 0, high = 6, опорный pivot = arr[6] = 7. Указатель i стартует с -1. Цикл j идёт от 0 до 5: j=0 (значение 8) не меньше опорного, пропуск; j=1 (2) меньше - i становится 0, обмен даёт [2,8,5,3,9,4,7]; j=2 (5) меньше - i=1, обмен: [2,5,8,3,9,4,7]; j=3 (3) меньше - i=2, обмен: [2,5,3,8,9,4,7]; j=4 (9) не меньше, пропуск; j=5 (4) меньше - i=3, обмен с arr[5]: [2,5,3,4,9,8,7].

После цикла (6 сравнений, 4 обмена) финальная перестановка меняет опорный arr[6]=7 местами с arr[i+1] = arr[4] = 9, давая [2,5,3,4,7,8,9] и возвращая pivotIndex = 4. Проверка: всё слева от индекса 4 ([2,5,3,4]) меньше 7, всё справа ([8,9]) больше - опорный на своём финальном месте, хотя обе стороны сами по себе ещё не отсортированы и требуют отдельной рекурсии.

Худший случай проявляется конкретно на уже отсортированном массиве при наивном выборе последнего элемента опорным. Для [1, 2, 3, 4, 5] (n = 5) опорный 5 всегда оказывается наибольшим, партиционирование даёт части размером n-1 и 0 на каждом шаге. Число сравнений на уровнях: 4 + 3 + 2 + 1 + 0 = 10, что равно n(n-1)/2 - той же формуле, что и у пузырьковой сортировки, и это ровно O(n²), а не O(n log n).

Схема партиционирования выше называется схемой Ломуто (по имени Ника Ломуто) - один указатель, простая для понимания, но делающая относительно много обменов. Оригинальная схема Хоара (её придумал сам Тони Хоар в 1961-м) использует два указателя, движущихся навстречу друг другу от обоих концов подмассива, и делает в среднем примерно втрое меньше перестановок за счёт того, что не гарантирует финальную позицию опорного, а лишь корректно разделяет подмассив.

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

Introsort, использующийся в libstdc++ для C++ std::sort, решает ту же проблему иначе: отслеживает глубину рекурсии и переключается на Heap Sort, если она превышает 2 * log2(n). Для n = 1000 порог составляет 2 * log2(1000) ≈ 19.93, то есть примерно 20 уровней - если Quicksort зашёл глубже, это верный признак систематически несбалансированных разбиений, и алгоритм страхуется гарантированным O(n log n) вместо риска квадратичного срыва.

Массивы с большим числом повторяющихся значений создают отдельную проблему: обычное двустороннее партиционирование продолжает рекурсивно дробить группу элементов, равных опорному, вместо того чтобы исключить её. Трёхстороннее партиционирование (Dutch national flag, по аналогии с тремя полосами голландского флага) делит подмассив на три зоны - «меньше», «равно», «больше» опорного - за один проход и рекурсирует только по крайним двум, полностью исключая среднюю зону из дальнейшей работы.

Quicksort известен с 1959 года, когда его придумал британский информатик Тони Хоар во время работы над машинным переводом в МГУ; опубликован алгоритм был в 1961-м под названием «Algorithm 64: Quicksort» в журнале Communications of the ACM. Название прижилось не случайно - на реальном железе он почти всегда обгоняет сортировку слиянием того же среднего порядка сложности именно за счёт партиционирования прямо в исходном массиве, без выделения временных буферов на каждом уровне рекурсии.

Нюансы выбора

Против Merge Sort - если O(n) дополнительной памяти merge sort недопустимо (большой массив в ограниченной памяти), Quicksort с его O(log n) на стек рекурсии - предпочтительный выбор, при условии что гарантия худшего случая не критична.

Против Heap Sort - Heap Sort гарантирует O(n log n) всегда и сортирует на месте с O(1) памяти, но его доступ к памяти скачет по индексам кучи, тогда как Quicksort обходит данные более последовательно. Когда гарантия важнее скорости - Heap Sort (или Introsort с его подстраховкой); когда важна типичная скорость - Quicksort.

На данных с большим числом повторов - стандартное двустороннее партиционирование (как в реализации на этой странице) деградирует к O(n²) на массиве, где почти все значения равны; здесь нужна модификация с трёхсторонним партиционированием, а не базовая схема Ломуто.

Не выбирать наивную версию для входа, который может быть адверсариальным (например, данные приходят от внешнего пользователя) - предсказуемый выбор опорного (первый/последний элемент) даёт атакующему возможность спровоцировать O(n²) заранее подготовленным входом; нужны либо случайный выбор опорного, либо Introsort с подстраховкой глубины.

На маленьких подмассивах (примерно до 10-20 элементов) накладные расходы на рекурсивные вызовы Quicksort перевешивают выигрыш от O(n log n) - гибридные реализации переключаются на Insertion Sort ниже этого порога, так же как это делают Timsort и Introsort.

Примеры в коде

Тони Хоар, 1959/1961 - Quicksort изобретён во время работы над проектом машинного перевода в МГУ и опубликован как «Algorithm 64: Quicksort» в Communications of the ACM - один из самых цитируемых алгоритмов сортировки в истории информатики.

libstdc++ (GCC) для `std::sort` реализует Introsort с конкретным порогом переключения на Heap Sort в 2 * log2(n) уровней глубины рекурсии - именно то число, которое проверяется в квизе этой страницы.

Dual-Pivot Quicksort (Владимир Ярославский, Йон Бенткус, Йозеф Бентли, 2009) используется в java.util.Arrays.sort(int[]) и других методах для примитивных типов в Java - вариант с двумя опорными элементами вместо одного, разбивающий массив сразу на три части за проход.

pdqsort (pattern-defeating quicksort, Орсон Питерс, 2015) используется в Rust'овом slice::sort_unstable - сочетает схему Хоара, эвристики обнаружения уже отсортированных участков и защиту от худшего случая по глубине, как у Introsort.

Атаки на алгоритмическую сложность (algorithmic complexity attacks) - в 2000-х исследователи показывали, что сервисы, принимающие пользовательские данные и сортирующие их наивным Quicksort с предсказуемым выбором опорного, можно положить заранее подготовленным входом, вызывающим O(n²) - это одна из причин, по которой современные стандартные библиотеки перешли на рандомизацию опорного или Introsort по умолчанию.

Когда применять

• Когда важна скорость на практике и сортировка «на месте», а гарантия худшего случая не критична (можно смягчить случайным выбором опорного).
• Для сортировки массивов примитивных типов в памяти, где произвольный доступ дешёв.

Примеры из практики

• `Array.prototype.sort` во многих движках JavaScript для примитивных типов исторически использовала варианты быстрой сортировки (сейчас чаще Timsort/гибриды).
• Introsort (используется в C++ std::sort) начинает с быстрой сортировки и переключается на heapsort, если рекурсия становится подозрительно глубокой - защита от худшего случая.