Быстрая сортировка: схема разбиения Ломуто, худший случай и рандомизация

Сортировка слиянием, которую мы разобрали в прошлом уроке, даёт гарантированное Θ(n log n) при любом входе — но за счёт O(n) дополнительного буфера. Quicksort предлагает другой договор: сортировка на месте, без отдельного буфера для слияния, но поведение зависит от того, насколько удачно выбран разделитель — pivot. Вся логика начинается с одной процедуры: разбиения массива вокруг pivot.

Схема разбиения Ломуто: инвариант и трассировка

Работаем с полуоткрытым отрезком [lo, hi) — соглашение, которое уже встречалось при бинарном поиске: правая граница hi не входит в подмассив, а элемент arr[hi-1] выбирается как pivot.

Два указателя делят отрезок на зоны. i начинается с lo - 1 и отмечает правую границу «всего, что уже не больше pivot». j идёт от lo до hi - 2 включительно и последовательно смотрит на каждый элемент: если arr[j] <= pivot — расширяем левую зону (i += 1) и меняем arr[i] с arr[j]; иначе — просто двигаем j дальше.

После того как j прошёл весь подмассив, pivot всё ещё лежит на arr[hi-1]. Один финальный обмен arr[i+1] ↔ arr[hi-1] ставит его на позицию p = i + 1. Это место — окончательное: pivot никогда больше не переместится.

def partition(arr: list, lo: int, hi: int) -> int:
    """Полуоткрытый [lo, hi). Возвращает финальный индекс pivot."""
    pivot = arr[hi - 1]
    i = lo - 1
    for j in range(lo, hi - 1):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[hi - 1] = arr[hi - 1], arr[i + 1]
    return i + 1

Инвариант после возврата:

• arr[lo : p] — все элементы <= pivot,
• arr[p] == pivot,
• arr[p+1 : hi] — все элементы > pivot.

Трассировка показывает, как сохраняется инвариант. arr = [3, 1, 4, 1, 5, 2], lo=0, hi=6, pivot = arr[5] = 2, i = -1.

j	arr[j]	действие	массив
0	3	3 > 2, пропуск	[3, 1, 4, 1, 5, 2]
1	1	1 ≤ 2 → i=0, swap arr[0]↔arr[1]	[1, 3, 4, 1, 5, 2]
2	4	4 > 2, пропуск	[1, 3, 4, 1, 5, 2]
3	1	1 ≤ 2 → i=1, swap arr[1]↔arr[3]	[1, 1, 4, 3, 5, 2]
4	5	5 > 2, пропуск	[1, 1, 4, 3, 5, 2]

Финальный swap arr[2] ↔ arr[5]: [1, 1, 2, 3, 5, 4]. Pivot на позиции p = 2.

Оба вхождения 1 оказались в левой части: условие <= отправляет туда все значения, равные pivot. Инвариант сохраняется, но большое число равных ключей может сделать разбиение несбалансированным.

Рекурсивная структура quicksort и базовый случай

После partition мы знаем позицию p: pivot уже стоит там, где ему положено быть в отсортированном массиве. Осталось упорядочить два независимых куска — [lo, p) и [p+1, hi) — и сделать это рекурсивно тем же способом.

def quicksort(arr: list, lo: int, hi: int) -> None:
    if hi - lo <= 1:          # 0 или 1 элемент — уже отсортировано
        return
    p = partition(arr, lo, hi)
    quicksort(arr, lo, p)     # левая часть: [lo, p)
    quicksort(arr, p + 1, hi) # правая часть: [p+1, hi)

Индекс p не входит ни в один рекурсивный вызов: pivot уже занимает окончательную позицию.

Глубина рекурсии определяется балансом полученных частей. Если каждый partition делит подмассив ровно пополам, получаем O(log n) уровней — то же дерево, что и у merge sort. Рекурсивные вызовы на каждом уровне суммарно обрабатывают все n элементов, и итог: O(n log n) операций.

Если pivot каждый раз оказывается на краю, например является минимальным элементом подмассива, Тогда левая часть пуста ([lo, p) содержит 0 элементов), а правая — n - 1 элементов. Глубина стека тогда растёт линейно: n непустых уровней вместо логарифмических.

Худший случай O(n²) и рандомизация pivot

Возьмём уже отсортированный массив [1, 2, 3, 4, 5] и фиксированный pivot = последний элемент. На первом вызове pivot = 5 — максимум, вся левая часть [1, 2, 3, 4], правая пуста. На втором pivot = 4, снова максимум. И так далее.

Стоимость разбиений: n-1 сравнений на первом уровне, n-2 на втором, ..., 1 на последнем. Сумма:

(n-1) + (n-2) + ... + 1 = n(n-1)/2 = Θ(n²)

Глубина стека при этом Θ(n) — каждый уровень оставляет один непустой подмассив размером на единицу меньше.

Наивное исправление — всегда брать средний элемент — не спасает: для специально подобранного входа его тоже можно превратить в максимум.

Рандомизация решает именно эту проблему: перед разбиением меняем случайный элемент arr[lo..hi-1] с arr[hi-1] и используем его как pivot.

import random

def partition_random(arr: list, lo: int, hi: int) -> int:
    r = random.randrange(lo, hi)
    arr[r], arr[hi - 1] = arr[hi - 1], arr[r]
    return partition(arr, lo, hi)

Для массива из n попарно различных ключей случайный pivot отвязывает выбор от порядка входа. Ожидаемое число сравнений — O(n log n), ожидаемая глубина стека — O(log n). Худшая цепочка по-прежнему возможна. Например, вероятность выбирать один из двух крайних по рангу элементов на каждом шаге и получить максимально несбалансированные разбиения равна 2^(n-1) / n! для попарно различных ключей.

Однако есть ситуация, которую рандомизация не лечит: массив из одинаковых ключей. Если все элементы равны pivot, то условие arr[j] <= pivot истинно для каждого j — вся левая часть заполнена, правая пуста. Получаем ровно ту же цепочку разбиений n-1/0, что и в худшем случае на различных ключах, и это происходит при любом выборе pivot. Рандомизация здесь бессильна, потому что проблема не в порядке, а в самих значениях.

Трёхчастное разбиение (< pivot, == pivot, > pivot) исключает весь блок равных pivot элементов из следующих рекурсивных вызовов. В этом уроке достаточно различать его с двухчастным Ломуто: вариант с <= не устраняет вырождение на большом числе дубликатов.

Сравнение quicksort и merge sort по памяти и гарантиям

Для случайного pivot и попарно различных ключей quicksort имеет ожидаемое время Θ(n log n), а merge sort гарантирует Θ(n log n) при любом порядке входа.

	Quicksort (random pivot, различные ключи)	Merge sort
Время, ожидаемое	Θ(n log n)	Θ(n log n)
Время, худшее	Θ(n²)	Θ(n log n)
Доп. память (данные)	Θ(1)	Θ(n)
Стек, ожидаемый	O(log n)	Θ(log n)
Стек, худший	Θ(n)	Θ(log n)
Стабильность	нет	да
Дубликаты (2-way Lomuto)	вырождение при всех равных	не влияет

Quicksort экономит память на самих данных: разбиение выполняется in-place и не требует линейного буфера. Стандартная реализация merge sort из предыдущего урока использует дополнительный буфер размером Θ(n).

Взамен quicksort отдаёт гарантии по времени: Θ(n log n) — ожидание по случайным выборам pivot для любого фиксированного входа с различными ключами, тогда как худший случай остаётся Θ(n²). Merge sort гарантирует Θ(n log n) при любом входе, поэтому подходит, когда важна детерминированная верхняя граница времени.

Стабильность merge sort означает, что равные элементы сохраняют исходный относительный порядок. Quicksort в классической реализации это не гарантирует: обмены во время разбиения могут переставить равные элементы произвольно.

Выбор зависит от контракта: quicksort полезен при требовании in-place и контролируемой стратегии pivot и дубликатов; merge sort — когда нужны стабильность или гарантированное Θ(n log n) время.