Кратко: быстрая сортировка (Quicksort) — разделяй-и-властвуй: выбрать опорный элемент (pivot), переставить элементы так, чтобы слева были ≤ pivot, справа — > pivot (partition), рекурсивно отсортировать две части.
Разбор на примере массива $[3,7,2,9,1,5]$. Возьмём простую схему Lomuto (pivot = последний элемент).
1) Исход: $[3,7,2,9,1,5]$, pivot $=5$.
Проход partition (переменная $i$ — индекс последнего элемента ≤ pivot, начинается $i=-1$):
- $j=0$: $3\le 5\Rightarrow i=0$, swap позиций $0$ и $0$ → $[3,7,2,9,1,5]$
- $j=1$: $7>5$ → ничего
- $j=2$: $2\le 5\Rightarrow i=1$, swap $1$ и $2$ → $[3,2,7,9,1,5]$
- $j=3$: $9>5$ → ничего
- $j=4$: $1\le 5\Rightarrow i=2$, swap $2$ и $4$ → $[3,2,1,9,7,5]$
После цикла swap $i+1=3$ с pivot → $[3,2,1,5,7,9]$. Pivot ($5$) оказался на позиции $3$.
2) Рекурсивные вызовы:
- Левая часть $[3,2,1]$ (индексы $0\dots 2$), pivot $=1$:
- partition даёт $[1,2,3]$, pivot на позиции $0$. Подмассивы пусты или длины 1, возвращаем.
- Правая часть $[7,9]$ (индексы $4\dots 5$), pivot $=9$: остаётся $[7,9]$.
Итог: $[1,2,3,5,7,9]$.
Анализ сложности:
- Среднее время: $O(n\log n)$. Формально среднее число сравнений $\Theta (n\log n)$.
- Худший случай: $O(n^2)$ (например, уже отсортированный массив + выбор крайнего pivot каждый раз).
- Память (рекурсивный стек): в среднем $O(\log n)$, в худшем $O(n)$ при сильно несбалансированных разбиениях.
Как уменьшить вероятность худшего случая:
- Случайный pivot (randomized quicksort) — ожидаемая сложность $O(n\log n)$.
- Median-of-three (первый/средний/последний) или выбор медианы по отбору (median of medians) для более сбалансированных разбиений.
Устойчивость (stable sort) и модификации:
- Обычный in-place Quicksort неустойчив. Возможные подходы для устойчивой версии:
1. Stable partition с дополнительной памятью: при разделении формировать три списка (меньше, равно, больше), добавлять элементы в исходном порядке и затем конкатенировать — это даёт устойчивую сортировку, но требует $O(n)$ дополнительной памяти.
2. «Декоративный» приём: сопоставить каждому элементу его исходный индекс и сортировать пары $(ключ,исходный\_индекс)$ по лексикографическому сравнению; итоговый порядок по ключу будет устойчивым (за счёт вторичного ключа). Нужна модификация компаратора, память как правило не увеличивается заметно.
3. Существуют in-place стабильные варианты quicksort, но они сложны и медленнее на практике; обычно предпочитают mergesort (стабильный и $O(n\log n)$ по времени, $O(n)$ по памяти) если нужна устойчивость.
Резюме: Quicksort на примере дал $[1,2,3,5,7,9]$. Средняя сложность $\Theta (n\log n)$, худшая $O(n^2)$. Для устойчивости проще использовать дополнительную память (stable partition) или применять стабильный алгоритм (mergesort) либо декорировать ключи индексами.