Кратко об алгоритме:
- Идея: выбрать опорный элемент (pivot), выполнить разбиение (partition) массива так, чтобы слева были элементы ≤ pivot, справа — ≥ pivot, затем рекурсивно отсортировать обе части.
- Типичный in-place вариант: Lomuto (проще) или Hoare (обычно быстрее и меньше обменов). После partition получается два подпроизведения, которые сортируются рекурсивно.
Основные шаги (схематично):
1. Выбрать pivot.
2. Разбить массив за $O(n)$ сравнений/перестановок.
3. Рекурсивно отсортировать левую и правую части.
Анализ сложности:
- Среднее время: $O(n\log n)$.
- Худшее время: $O(n^2)$ (при очень неудачном выборе pivot).
- Рекуррентное соотношение для общего случая: $T(n)=T(k)+T(n-k-1)+\Theta (n)$, где $k$ — размер левой части после partition.
- В худшем (например $k=0$ всегда): $T(n)=T(n-1)+\Theta (n)=\Theta (n^2)$.
- Память: средне $O(\log n)$ для стека вызовов (балансные разбиения), в худшем $O(n)$.
Поведение на уже отсортированных массивах:
- Если pivot выбирается как первый или последний элемент, то для уже отсортированного (или обратно отсортированного) массива partition всегда даёт одну пустую и одну почти полную часть ($k=0$), поэтому время становится $\Theta (n^2)$.
- Если используется случайный выбор pivot или стратегии вроде median-of-three (сравнить первый, средний, последний и выбрать медиану), то для отсортированного входа ожидается сбалансированное разбиение и время вернётся к $\Theta (n\log n)$.
Поведение на почти отсортированных массивах:
- При плохом выборе pivot (например, всегда первый элемент) почти отсортированные входы обычно приводят к плохому балансированию и близки к худшему случаю $O(n^2)$.
- Случайный pivot или median-of-three делают quicksort устойчивым к почти отсортированным данным — обычно $O(n\log n)$.
- Для массивов с небольшим числом «переставленных» элементов некоторые алгоритмы (например, insertion sort) работают лучше; поэтому практические реализации часто:
- переключаются на insertion sort для маленьких подмассивов (порог ~$16$–$32$),
- используют случайный pivot или median-of-three,
- применяют three-way partitioning (Дженгоа/Дутча) при множестве равных элементов,
- используют introsort (переход на heapsort при слишком большой глубине рекурсии) для гарантированной $O(n\log n)$ в худшем случае.
Коротко о практических рекомендациях:
- Не выбирать всегда первый/последний элемент как pivot на практике.
- Для устойчивости к отсортированным/почти отсортированным данным: использовать рандомизацию или median-of-three, порог для insertion sort и/или introsort. Quicksort при этих улучшениях обычно очень быстрый и практичен.