Худший случай быстрой сортировки и как его избегают

Если ты понимаешь, откуда у быстрой сортировки берётся Θ(n²), почему выбор первого элемента опорным ломается на отсортированном входе и как это лечат (случайный опорный, медиана трёх, переключение), листай до «Теперь сам».

Как думаешь, всегда ли быстрая сортировка быстрая

Название обманывает: «быстрая» она в СРЕДНЕМ, а не всегда. Весь её выигрыш держится на одном допущении - что опорный делит массив примерно пополам. Тогда уровней рекурсии log n, и всё хорошо. Но что если опорный делит плохо - отрезает не половину, а один элемент? Тогда вместо log n уровней их становится n, и на каждом всё ещё Θ(n) работы. Прикинь, во что это выльется, - и увидишь, что «быстрая» умеет быть квадратичной.

На что это похоже

Ты делишь колоду пополам, чтобы искать быстрее. Но если каждый раз ты «делишь», отрезая одну верхнюю карту, а остальное оставляешь одной кучей, - ты не делишь, а снимаешь по карте. Чтобы разобрать всю колоду так, понадобится столько шагов, сколько карт, и на каждом ты ещё просматриваешь всю оставшуюся кучу. Деление пополам экономит, а деление «одна против всех» - нет: получается перебор, только с лишними накладными расходами.

Механизм: откуда берётся Θ(n²)

Пусть опорный всякий раз оказывается наименьшим элементом части. Тогда разбиение кладёт его на первое место, слева от него - пусто (нет меньших), справа - все остальные n − 1. Следующий вызов работает с n − 1 элементами и повторяет то же. Получается рекуррентность T(n) = T(n−1) + n (одно разбиение стоит Θ(n), а рекурсия идёт по почти всему массиву): это вычитание, а не деление, и оно даёт n + (n−1) + ... + 1 = Θ(n²) - знакомый арифметический ряд из раздела про рекуррентности. Дерево рекурсии выродилось из куста в ЦЕПОЧКУ длины n. Хуже того: n вложенных вызовов - это n кадров на стеке, и на большом массиве стек может переполниться.

Правило

Быстрая сортировка Θ(n·log n) только когда опорный делит массив примерно пополам. Если опорный раз за разом почти минимален/максимален, разбиение отрезает по одному элементу, дерево вырождается в цепочку длины n и выходит Θ(n²) (плюс риск переполнить стек рекурсией глубины n). Выбор ПЕРВОГО элемента опорным даёт худший случай на уже отсортированном входе. Лечится выбором опорного и защитой глубины рекурсии.

Разбор: почему именно отсортированный вход ломает «первый элемент»

Если опорным всегда берут первый элемент a[low], то на уже отсортированном (по возрастанию) массиве первый элемент - это МИНИМУМ. Разбиение отрезает его одного, справа остаётся n − 1 больших, и следующий вызов снова берёт минимум остатка. Так на каждом шаге отрезается по одному - Θ(n²). То же на отсортированном ПО УБЫВАНИЮ (первый - максимум). Злая ирония: самый «удобный» на вид вход - уже упорядоченный - оказывается для наивной быстрой сортировки худшим. А ведь почти упорядоченные данные в жизни встречаются сплошь и рядом (дозаписали в отсортированный список) - поэтому наивный выбор опорного не просто теоретически плох, он подрывается на типичных реальных данных.

Разбор: три способа вылечить

Случайный опорный. Берём опорным СЛУЧАЙНЫЙ элемент части, а не первый. Тогда никакой конкретный вход (в том числе отсортированный) не будет стабильно плохим: противник не может заранее подстроить массив под наш выбор. Худший случай Θ(n²) формально остаётся возможным, но его вероятность ничтожна - ожидаемое время Θ(n·log n) на ЛЮБОМ входе.

Медиана трёх. Берём три элемента (первый, средний, последний), опорным делаем их МЕДИАНУ (средний по величине). Это дёшево и почти всегда даёт неплохое деление; заодно чинит именно отсортированный вход (там медиана трёх - настоящий средний элемент, деление пополам).

Переключение при глубокой рекурсии (introsort). Следим за глубиной рекурсии; если она превысила ~2·log n (признак, что опорные делят плохо), переключаемся на сортировку с ГАРАНТИЕЙ n·log n - обычно пирамидальную (следующая глава). Так быстрая сортировка получает и свою среднюю скорость, и защиту от Θ(n²). Именно так устроены промышленные реализации.

Что ломается без этого

Главная беда - наивная быстрая сортировка с опорным-первым в проде: она отлично работает на тестах со случайными данными и внезапно деградирует до Θ(n²) (и до переполнения стека) на отсортированном или почти отсортированном входе - а такие входы в жизни обычны. Это классический источник «внезапно всё повисло на реальных данных, хотя на тестах летало». Вторая ошибка - думать, что случайный опорный делает худший случай НЕВОЗМОЖНЫМ: он делает его лишь крайне маловероятным; строгую гарантию n·log n даёт переключение на пирамидальную или сортировка слиянием.

Зачем это в работе

Это причина, по которой в реальных библиотеках почти никогда не встретишь «учебную» быструю сортировку с опорным-первым. Стандартные реализации (например, introsort в C++) берут медиану, при необходимости случайность и обязательно защищают глубину рекурсии переключением на пирамидальную - получая среднюю скорость быстрой сортировки И гарантию n·log n в худшем случае. Практический вывод для тебя: если пишешь сортировку сам (что редко нужно), никогда не бери опорным просто первый элемент; а лучше - используй встроенную, она уже всё это учла. И помни: «в среднем n·log n» - это обещание про случайные входы, а реальные данные часто не случайны.

Теперь сам

Наивная быстрая сортировка берёт опорным первый элемент. Ей дали уже отсортированный [1, 2, 3, 4, 5]. Опиши, как пойдёт рекурсия и почему выйдет Θ(n²), а не Θ(n·log n).