Причины деградации до $O(n^2)$
- Плохой выбор опорного элемента: если опора каждый раз оказывается минимумом или максимумом, разбиения имеют размеры $0$ и $n-1$. Тогда рекуррентное соотношение
$$T(n)=T(n-1)+\Theta (n)$$ даёт $T(n)=\Theta (n^2)$. Конкретные входы: уже отсортированный или обратно отсортированный массив при выборе опоры как первого/последнего элемента.
- Много одинаковых ключей: при стандартном двухсекторном partition элементы, равные опоре, могут уходить в одну сторону, и количество элементов уменьшается лишь на единицу за шаг — тоже даёт $O(n^2)$ на входах с множественными дубликатами (например, все элементы равны).
- Адвёрсарные входы для детерминированных эвристик (напр., специально составленные последовательности, которые ломают median-of-three).
- Глубокая рекурсия/стек при плохом балансе (риск переполнения стека).
Модификации для стабилизации времени работы
1) Случайный выбор опоры (рандомизированный quicksort)
- В каждом partition выбирать опору случайно (или обменять случайный элемент с первым перед partition).
- Гарантии: ожидаемое время $O(n\log n)$ и высокие шансы на близкие к средним разбиения. Простая, эффективная в практике защита от худших входов.
2) Предварительная случайная перестановка (Fisher–Yates shuffle)
- Перемешать массив один раз за $O(n)$, затем применять обычный quicksort (даже если опора — первый/последний элемент).
- Гарантия: порядок ввода больше не влияет, ожидаемое время $O(n\log n)$.
3) Эвристики выбора опоры
- Median-of-three: выбрать медиану из первого, среднего и последнего элементов как опору. Уменьшает вероятность крайних разбиений на частично отсортированных данных; простой и дешёвый.
- Median-of-medians (детерминированный выбор квазимедианы): даёт гарантированные приближённо сбалансированные разбиения (например, гарантирует, что одна часть не больше некоторой доли $<1$ от $n$), что приводит к детерминированному времени $O(n\log n)$ (с большими константами). Используется редко в практических реализациях из-за накладных расходов.
4) $3$-way partition (Dutch national flag) для множества дублей
- Разбить на три части: \ опора. Псевдокод основной идеи:
- инициализировать $lt=lo,i=lo,gt=hi,pivot=A[lo]$ - пока $i\le gt$:
- если $A[i]<pivot$ — swap($A[lt],A[i]$); $lt++;i++$ - иначе если $A[i]>pivot$ — swap($A[i],A[gt]$); $gt--$ - иначе $i++$ - рекурсивно сортировать диапазоны $[lo,lt-1]$ и $[gt+1,hi]$ - Эффект: при большом количестве одинаковых элементов алгоримт работает значительно быстрее (в пределе — линейно $O(n)$ если все элементы равны).
5) Introsort (гибридный подход)
- Запускают quicksort, отслеживают глубину рекурсии; при превышении порога (например, $c\log n$) переключаются на heapsort. Это даёт гарантированное худшее время $O(n\log n)$ и практическую скорость quicksort.
Дополнительные практические рекомендации
- Для конкурентной реализации — итеративный код/элиминация хвостовой рекурсии, сортировать сначала меньшую часть, рекурсировать в меньшей глубине, это уменьшает стек.
- В большинстве реализаций комбинируют: сначала shuffle или случайный опорный элемент, использовать median-of-three как эвристику, применять $3$-way partition при ожидании дубликатов, и introsort для гарантии худшего случая.
Кратко: основные причины — систематически неудачный выбор опоры и много дубликатов. Простые и эффективные меры: выбор опоры случайно или предварительная перестановка, $3$-way partition для дублей, median-of-three/median-of-medians или introsort для жёстких гарантий.