Кратко — три практических подхода и доказательства/инварианты для каждого.
1) Рандомизация (случайный выбор опорного элемента или предварительное случайное перемешивание)
- Идея: выбирать опорный элемент uniformly at random (или заранее перемешать массив). Это убирает зависимость от входа и делает «плохие» разбиения маловероятными.
- Формулы/оценки:
- Для количества сравнений $C_n$ справедливо стандартное ожидание
$$\mathbb{E}[C_n]=2(n+1)H_n-4n=O(n\log n),$$ где $H_n$ — гармонический ряд.
- Рекуррент для ожидаемого времени:
$$\mathbb{E}[T(n)]=n-1+\frac{1}{n}\sum _{k=0}^{n-1}(\mathbb{E}[T(k)]+\mathbb{E}[T(n-1-k)])=O(n\log n).$$ - Высокая вероятность (tail bound): пометив разбиения «хорошими», если разбиение уменьшает размер не менее чем в константный фактор (например, до $\le 3/4$ от размера), вероятность «хорошего» разбиения $\ge 1/2$. По концентрации (Chernoff) число хороших разбиений на пути глубиной $c\log n$ концентрируется вокруг своего ожидания, следовательно глубина рекурсии $O(\log n)$ с вероятностью $1-n^{-\Omega (1)}$. Итого: вероятность квадратичной сложности экспоненциально мала в логарифме размера входа.
- Инвариант корректности: шаг partition помещает опорный элемент в его окончательную позицию и сохраняет классификацию элементов pivot; по индукции алгоритм корректен.
2) Медиана медиан (детерминированный выбор хорошего опорного — BFPRT)
- Идея: использовать алгоритм выбора порядка статистики за $O(n)$ (группировать по 5, взять медианы, рекурсивно вычислить медиану медиан) и использовать её как опорный элемент. Это даёт детерминированную гарантию «неплохого» разбиения.
- Ключевое свойство (группа по 5): для массива размера $n$ медиана медиан гарантирует, что по меньшей мере $3\lfloor n/10\rfloor$ элементов $\le$ ей и по меньшей мере $3\lfloor n/10\rfloor$ $\ge$ ей. Следовательно размер каждой части после partition не превосходит $7n/10$.
- Рекуррент для времени (quicksort с таким выбором опорного):
$$T(n)\le 2T(7n/10)+O(n).$$ По стандартному решению рекуррентов получаем $T(n)=O(n\log n)$ — жёсткая детерминированная гарантия.
- Инвариант корректности: тот же partition-инвариант; дополнительная гарантия по балансу разбиения даёт асимптотическую верхнюю границу на глубину рекурсии.
- Замечание: константы и накладные расходы у BFPRT больше, поэтому в практике часто используют смешанные схемы (медиана из 3, перемешивание) вместо чистого медиана-медиан.
3) Интроспекция (Introsort)
- Идея: исполнять быстрый (рандомизированный или детерминированный) quicksort, но отслеживать максимальную глубину рекурсии; если глубина превышает порог (обычно $c\log n$, часто $2\lfloor {\log }_{2}n\rfloor$), перейти на алгоритм с гарантированным худшим случаем $O(n\log n)$ (обычно heapsort).
- Гарантии:
- Быстродействие на «хороших» данных равно быстрому варианту (обычно $O(n\log n)$ с хорошими константами).
- В худшем случае (если много плохих разбиений) переключение гарантирует окончательное время $O(n\log n)$ (по свойствам heapsort).
- Инвариант корректности: swap/partition-инвариант сохраняется, а переключение не нарушает покрытие всех элементов и корректность результата.
- Практическое применение: Introsort (используемый в std::sort) даёт и лучшие практические константы quicksort, и детерминированную гарантию худшего случая через heapsort.
Короткие рекомендации и комбинации:
- Для практики: перемешивание + медиана из трёх + порог на малые подмассивы (insertion sort) + introsort для безопасности.
- Для теоретически жёсткой гарантии по худшему случаю: использовать медиана-медиан (BFPRT) для выбора опорного или introsort (переключение на heapsort).
Вывод (формулировка преимуществ):
- Рандомизация: устраняет плохие входы, даёт $E[T]=O(n\log n)$ и «высокую вероятность» $O(n\log n)$.
- Медиана медиан: даёт детерминированную гарантию $O(n\log n)$ в худшем случае (за счёт больших констант).
- Интроспекция: сочетает практическую эффективность quicksort и жёсткую гарантированную верхнюю оценку через переключение на heapsort.