Быстрая сортировка

Быстрая сортировка (quicksort) выбирает опорный элемент (pivot), делит массив на «не больше опорного» и «больше опорного» и рекурсивно сортирует части. В среднем $O(N\log N)$, в худшем $O(N^2)$, без буфера.

Зачем нужно

Сортировка слиянием гарантирует $O(N\log N)$, но требует буфер на $O(N)$ и копирует все элементы туда и обратно. Быстрая сортировка переставляет элементы на месте. Асимптотика в среднем та же, константа обычно меньше — разные сортировки, разные константы.

Как работает

Вся работа — в Partition (разбиении). Слияния после рекурсии нет: когда части отсортированы, весь отрезок уже отсортирован.

Схема с Partition Ломуто

Partition(arr, left, right)       // [left, right)
    p = arr[right − 1]
    i = left
    for j = left ... right − 2
        если arr[j] ≤ p
            swap(arr[i], arr[j])
            i++
    swap(arr[right − 1], arr[i])
    return i
 
Qsort(arr, left, right)
    если left ≥ right
        return
    id_p = Partition(arr, left, right)
    Qsort(arr, left, id_p)
    Qsort(arr, id_p + 1, right)

Инвариант Ломуто — четыре зоны: [left, i) $\le p$, [i, j) $>p$, [j, right−1) не обработаны, arr[right−1] = p. После цикла $p$ ставится между зонами и больше не двигается — поэтому в рекурсию он не идёт, и обе части строго короче отрезка. Доказательство — в конспекте.

Partition Хоара

Два указателя идут навстречу: L пропускает элементы $<p$, R — элементы $>p$, остановившиеся меняются местами. Результат: [left, R] $\le p$, [R+1, right) $\ge p$, но опорный не обязательно на позиции R. Поэтому рекурсия другая:

Partition(arr, left, right)
    p = arr[(left + right − 1) / 2]
    L = left;  R = right − 1
    while (true)
        пока arr[L] < p: L++
        пока arr[R] > p: R--
        если L ≥ R: return R
        swap(arr[L], arr[R]);  L++;  R--
 
Qsort(arr, left, right)
    если right − left ≤ 1: return
    R = Partition(arr, left, right)
    Qsort(arr, left, R + 1)
    Qsort(arr, R + 1, right)

На лекции Хоар записан с ошибками

На доске Хоар подставлен в схему Qsort для Ломуто (опорный выкидывается из рекурсии), а середина взята как (left + right) / 2. Первое даёт неотсортированный результат, второе после исправления рекурсии — бесконечную рекурсию на [1, 2]. Версия выше — исправленная и проверенная. Разбор — в конспекте.

Выбор опорного

С лекции: первый, последний, средний элемент, медиана трёх (первого, среднего, последнего), случайный. Для подотрезка — arr[left], а не arr[0].

Асимптотика

Случай	$T(N)$	Память на стек
разбиение примерно пополам	$O(N\log N)$	$O(\log N)$
опорный — всегда крайний по величине	$O(N^2)$	$O(N)$
случайный опорный, в среднем	$O(N\log N)$	$O(\log N)$

Partition — $O(N)$ на уровень рекурсии. Уровней $\log N$, если делится ровно, и $N$, если одна часть каждый раз пустая.

Не из лекции: оценки

• Худший случай: $(N-1)+(N-2)+\dots +1=N(N-1)/2$. Ломуто с последним элементом на отсортированном массиве — ровно так: на $N=4000$ 7 998 000 сравнений.
• Случайный опорный: $z_i$ и $z_j$ сравниваются с вероятностью $\frac{2}{j-i+1}$ — когда одним из них выбран первый опорный в группе $z_i,\dots ,z_j$. Сумма по парам — не больше $2N{H}_N=O(N\log N)$. Подробно — в конспекте, раздел 6.
• Равные элементы: Ломуто с ≤ на массиве одинаковых чисел вырождается в $O(N^2)$, Хоар делит пополам (55 454 сравнения на тех же 4000 элементах).

Тонкости

• В таблице лекции у быстрой сортировки $M(N)=O(1)$ — это без стека рекурсии. Partition работает на месте, но глубина рекурсии — память.
• Быстрая сортировка неустойчива: обмены перебрасывают элементы через весь отрезок.
• Это сортировка сравнением, и нижняя оценка $\Omega (N\log N)$ из Сортировка к ней относится.

Не из лекции

Неустойчивость: [2a, 2b, 1] у Ломуто с опорным 1. Оба элемента $>1$, цикл ничего не меняет, а финальный swap(arr[right − 1], arr[i]) при $i=0$ меняет 1 с 2a: получается [1, 2b, 2a].

Частые ошибки

• Использовать рекурсию Ломуто (без опорного) с Partition Хоара.
• Брать опорным крайний элемент — и получать $O(N^2)$ на отсортированном входе.
• Писать arr[0] вместо arr[left] в подотрезке.
• Считать, что быстрая сортировка гарантирует $O(N\log N)$.
• Забывать, что у Ломуто на одинаковых элементах тот же худший случай.