Ключевая идея: сложность быстрой сортировки определяется тем, насколько равномерно разбиение при выборе опорного элемента (pivot). Опорный элемент задаёт размеры двух подмассивов после partition; чем ближе они к одинаковым — тем глубже сбалансированное дерево рекурсии и ниже время.
Как выбор pivot влияет на сложность
- Средний случай. При «хорошем» (в среднем — случайном) выборе pivot размеры подмассивов в среднем пропорциональны $\Theta (n)$ так, что рекуррентное соотношение даёт
$$E[T(n)]=O(n\log n),$$ а ожидаемое число сравнений для случайного pivot приближённо равно
$$E[C_n]\approx 2n\ln n(\approx 1.386n{\log }_{2}n).$$
- Худший случай. Если pivot постоянно оказывается крайним элементом (минимум или максимум) — например, при выборе первого/последнего элемента на уже отсортированном массиве — рекуренция
$$T(n)=T(n-1)+O(n)$$ даёт
$$T(n)=O(n^2).$$ То есть плохой выбор pivot приводит к квадратичной сложности.
Предложения по улучшению и обоснование
1. Рандомизация pivot
- Метод: выбирать pivot случайно (или перемешать массив перед сортировкой).
- Эффект: устраняет зависимость от входа, даёт ожидаемую сложность $O(n\log n)$ и высокий шанс сбалансированных разбиений. Простая и эффективная на практике.
2. Median-of-three
- Метод: выбирать медиану из трёх элементов (обычно первый, средний, последний).
- Эффект: уменьшает вероятность очень неравномерных разбиений, особенно на частично отсортированных входах, с небольшой дополнительной затратой на выбор pivot. Практически улучшает константы.
3. Трёхсторонняя (Dutch national flag) партияция
- Метод: разделять на три части: pivot.
- Эффект: при множестве равных ключей даёт значительное ускорение; в предельных случаях с большим числом дубликатов сложность может стать близкой к $O(n)$ вместо $O(n\log n)$.
4. Интроспективная сортировка (Introsort)
- Метод: стартовать как quicksort, но при превышении порога глубины рекурсии (обычно $c\log n$) переключиться на heapsort.
- Эффект: сохраняет практические преимущества quicksort и гарантирует в худшем случае $O(n\log n)$. Именно так реализован std::sort в C++.
5. Детерминированный выбор медианы (median-of-medians)
- Метод: алгоритм выбора медианы за $O(n)$ времени применяется для pivot, даёт гарантированно хорошее разбиение.
- Эффект: обеспечивает детерминированное $O(n\log n)$ в худшем случае, но с большими константами; редко используется в практических реализациях quicksort из‑за накладных расходов.
6. Комбинация с insertion sort для малых подмассивов
- Метод: при размере подмассива $\le t$ (обычно $t\approx 10\dots 50$) использовать insertion sort.
- Эффект: уменьшает константы и ускоряет сортировку на небольших сегментах, где insertion sort эффективнее.
7. Хвостовая рекурсия и рекурсия по меньшей части
- Метод: рекурсивно обрабатывать всегда меньший из двух подмассивов, а больший обрабатывать в цикле (tail recursion elimination).
- Эффект: гарантирует глубину стека $O(\log n)$ при «обычных» разбиениях.
Рекомендация на практике
- Для большинства задач: использовать randomized pivot или median-of-three + тристороннюю партицию + переход на insertion sort для маленьких частей + хвостовую оптимизацию.
- Если нужна строгая гарантия по худшему случаю: применять introsort (quicksort + переключение на heapsort) или использовать median-of-medians (с учётом больших констант).
Кратко: плохой pivot → рекурсия глубиной $O(n)$ → $O(n^2)$; хороший/случайный pivot → сбалансированные разбиения → $O(n\log n)$. Улучшения (рандомизация, median-of-three, 3-way partition, introsort, insertion switch) либо снижают вероятность худшего случая, либо дают детерминированную гарантию с приемлемыми практическими константами.