Быстрая сортировка: почему возникает худший случай

Быстрая сортировка (quicksort) в среднем работает за $O(n\log n)$ и на практике часто быстрее других сортировок сравнения, но у неё есть слабое место: при неудачном выборе опорного элемента время работы деградирует до $O(n^2)$. Это не редкое исключение, а вполне предсказуемая ситуация - она возникает, например, когда наивная реализация берёт опорным элементом всегда первый элемент подмассива, а на вход подаётся уже отсортированный массив. Ниже разберём, откуда берётся это разбиение (0, n-1), как вывести формулу сложности худшего случая, чем он отличается от среднего и как реальные реализации от него защищаются. Чтобы сразу увидеть разницу в числах, поменяй параметры в калькуляторе ниже: он показывает число сравнений и глубину рекурсии для выбранного размера массива, стратегии выбора опорного элемента и порядка входных данных.

Как устроена быстрая сортировка

Алгоритм рекурсивно применяет одну и ту же схему к массиву (или подмассиву): выбрать опорный элемент, разбить (partition) массив на две части - меньше опорного и больше опорного, - затем рекурсивно отсортировать обе части. Разбиение делается за линейное время: один проход по подмассиву переставляет элементы так, что опорный оказывается на своём финальном месте, слева от него все элементы меньше, справа - больше. Никакого слияния, как в сортировке слиянием, не требуется - весь массив сортируется на месте (in-place).

Ключевой параметр, определяющий скорость работы, - это баланс разбиения. Если опорный элемент оказывается медианой (или близко к ней), обе части получаются примерно равного размера, и рекурсия быстро сходится. Если же опорный оказывается минимумом или максимумом текущего подмассива, одна часть остаётся пустой, а вторая - размером n-1: рекурсия почти не сокращает задачу.

Почему возникает худший случай

Худший случай возникает не из-за размера входных данных, а из-за сочетания способа выбора опорного элемента и порядка массива. Самый частый пример: опорным берётся первый элемент подмассива, а массив уже отсортирован по возрастанию. Тогда на первом шаге опорный - это глобальный минимум: разбиение даёт пустую левую часть и правую часть из n-1 элементов. На следующем шаге ситуация повторяется - опорный снова оказывается минимумом оставшегося подмассива. Так происходит на каждом уровне рекурсии, и дерево вызовов вместо сбалансированного дерева глубины $\log_2 n$ превращается в цепочку глубины n-1.

Рассчитать для своей задачи

Точно так же вырождается и обратно отсортированный массив, если опорный элемент постоянно оказывается максимумом. Важно понимать: сама по себе быстрая сортировка не "плохая" - плохим оказывается конкретное сочетание стратегии выбора опорного элемента и структуры данных, которое легко случайно воспроизвести на практике (отсортированные логи, уже частично упорядоченные списки).

Вывод сложности худшего случая

Обозначим через $T(n)$ время работы на массиве из n элементов. Разбиение (partition) всегда стоит $O(n)$ - линейный проход. В худшем случае одна часть пустая, вторая содержит n-1 элементов, поэтому рекуррентное соотношение выглядит так:

$$T(n) = T(n - 1) + T(0) + O(n) = T(n-1) + O(n).$$

Раскроем рекурсию суммированием, считая, что на каждом уровне тратится порядка $c \cdot n$ операций на само разбиение:

$$\begin{aligned} T(n) &= c\,n + T(n-1) \\ &= c\,n + c\,(n-1) + T(n-2) \\ &= c\,n + c\,(n-1) + c\,(n-2) + \dots + c\,1 \\ &= c \cdot \frac{n(n-1)}{2}. \end{aligned}$$

Получаем $T(n) = O(n^2)$: число сравнений в худшем случае равно сумме арифметической прогрессии $n(n-1)/2$, а глубина рекурсии равна ровно $n-1$, потому что каждый вызов уменьшает размер задачи только на один элемент. Например, для массива из 16 элементов это $16 \cdot 15 / 2 = 120$ сравнений и 15 уровней рекурсии - калькулятор выше считает эти же числа для любого n, которое ты выберешь.

Средний случай: почему это O(n log n)

Если опорный элемент выбирается случайно (или используется медиана трёх), в среднем разбиение получается сбалансированным: обе части примерно равны n/2. Тогда рекуррентное соотношение другое:

$$T(n) = 2\,T\!\left(\frac{n}{2}\right) + O(n),$$

и по основной теореме о рекуррентных соотношениях (master theorem) это даёт $T(n) = O(n\log n)$. Глубина рекурсии в этом случае - около $\log_2 n$, потому что каждый уровень делит оставшийся размер задачи пополам, а не на единицу.

Рассчитать для своей задачи

Разница между $n\log_2 n$ и $n(n-1)/2$ выглядит небольшой на маленьких n, но растёт стремительно: уже при n = 200 среднее число сравнений порядка 1500, а худшее - почти 20000. Именно эту кривую роста и рисует график в калькуляторе выше при передвижении ползунка размера массива.

Как избежать худшего случая на практике

Раз худший случай определяется совпадением стратегии выбора опорного элемента и структуры входных данных, разработчики защищаются именно на уровне выбора опорного элемента:

• Случайный опорный элемент. Перед разбиением опорный элемент выбирается случайным индексом. Тогда вероятность подряд получить вырожденное разбиение на всех уровнях рекурсии исчезающе мала - независимо от того, отсортирован входной массив или нет.
• Медиана трёх (median-of-three). Берутся первый, средний и последний элементы подмассива, и опорным становится их медиана. Такой выбор специально противостоит уже отсортированным и обратно отсортированным массивам - как раз тем входам, на которых чаще всего ловится наивная реализация с фиксированным опорным элементом.
• Переключение на другую сортировку на малых подмассивах. Многие библиотечные реализации при размере подмассива меньше 10-16 элементов переключаются на сортировку вставками - она быстрее на маленьких n и не подвержена такому вырождению.
• Intro-сортировка (introsort). Отслеживает глубину рекурсии и, если она превышает $2\log_2 n$ (сигнал, что разбиение стало плохим), переключается на пирамидальную сортировку с гарантией $O(n\log n)$ в худшем случае. Так устроена сортировка в стандартных библиотеках C++ и .NET.

Пример: сортировка отсортированного массива

Возьмём массив из 10 уже отсортированных по возрастанию элементов и наивную реализацию с опорным - первым элементом. На первом шаге опорный равен минимальному значению массива, разбиение даёт пустую левую часть и правую из 9 элементов. На втором шаге - снова минимум оставшихся 9, правая часть из 8 элементов, и так далее. Число сравнений на partition каждого уровня равно размеру текущего подмассива минус один: $9 + 8 + 7 + \dots + 1 = 45 = 10 \cdot 9 / 2$, что и совпадает с формулой худшего случая.

Если тот же массив прогнать со случайным опорным элементом, типичное разбиение окажется куда ближе к 50/50: скажем, 4 и 5 элементов на первом шаге, затем снова примерно пополам - глубина рекурсии для 10 элементов останется в районе 3-4 уровней вместо 9, а не наоборот, число сравнений упадёт примерно втрое. Подставь n = 10 в калькулятор выше и переключи стратегию опорного элемента и порядок массива, чтобы увидеть эту разницу в конкретных числах.

Частые ошибки

• Считать быструю сортировку гарантированно $O(n\log n)$. Это верно только для среднего случая; худший случай $O(n^2)$ реален и легко воспроизводится на отсортированных данных при наивном выборе опорного элемента.
• Путать глубину рекурсии со сложностью алгоритма. Глубина рекурсии в худшем случае равна n-1, а не $\log_2 n$ - это разные величины, и именно рост глубины стека вызывает не только медленную работу, но и риск переполнения стека на больших n.
• Забывать про пустые подмассивы при подсчёте сравнений. В худшем случае одна из частей разбиения всегда пустая (0 элементов), поэтому рекурсия не "экономит" работу - следующий вызов почти не уменьшился в размере.
• Игнорировать структуру входных данных. Оценка сложности алгоритма не может опираться только на размер n - нужно учитывать конкретные свойства входа (уже отсортирован, содержит много повторов и так далее).
• Считать медиану трёх абсолютной защитой. Она резко снижает вероятность худшего случая на практике, но не исключает его математически - специально сконструированный вход всё ещё может его вызвать.

FAQ

Почему быстрая сортировка вообще используется, если у неё есть худший случай $O(n^2)$? Потому что на практике (со случайным или медианным опорным элементом) средний случай $O(n\log n)$ выполняется с маленькой константой и хорошей локальностью памяти, поэтому quicksort часто обгоняет сортировку слиянием и пирамидальную сортировку, у которых гарантия $O(n\log n)$ жёстче, но константа обычно больше.

Чему равно число сравнений в худшем случае для массива из 100 элементов? По формуле $n(n-1)/2$ получаем $100 \cdot 99 / 2 = 4950$ сравнений - подставь n = 100 в калькулятор выше, чтобы увидеть это же число и сравнить с оценкой среднего случая.

Всегда ли отсортированный массив даёт худший случай быстрой сортировки? Нет, только если опорный элемент выбирается детерминированно как первый (или последний) элемент подмассива. При случайном опорном элементе или медиане трёх отсортированный массив ничем не хуже случайного - вырождение специально устранено выбором стратегии.

Коротко

Худший случай быстрой сортировки $O(n^2)$ возникает, когда опорный элемент раз за разом оказывается минимумом или максимумом текущего подмассива - типичный пример: опорный - первый элемент на уже отсортированном массиве. Рекуррентное соотношение $T(n) = T(n-1) + O(n)$ раскрывается в сумму арифметической прогрессии $n(n-1)/2$, тогда как сбалансированное разбиение при случайном опорном элементе или медиане трёх даёт $T(n) = 2T(n/2) + O(n) = O(n\log n)$. На практике от вырождения защищаются рандомизацией выбора опорного элемента, медианой трёх и переключением на другие алгоритмы при плохих признаках - именно так устроены быстрые сортировки в стандартных библиотеках.