Рандомизация, быстрая сортировка и выбор статистики

В прошлой лекции куча дала сортировку с гарантией O(n log n). Теперь рассмотрим другой способ делить задачу на части. Он приведёт и к сортировке, и к поиску одного нужного элемента, а для хорошей скорости мы сначала разрешим алгоритму делать случайный выбор.

Возьмём [1,2,3,4,5,6,7,8,9]. Опора 1 оставляет восемь больших элементов; опора 5 делит внешние части по четыре; случайная опора может дать любой из этих случаев. Сначала сравните реальные запуски на одном входе.

Рандомизированный алгоритм (Randomized algorithm) — Алгоритм, который помимо входных данных использует случайные биты или случайный выбор.

У детерминированного алгоритма один и тот же вход вызывает одну и ту же последовательность действий. У рандомизированного действия могут отличаться между запусками. При этом случайность не обязана влиять на правильность ответа: рассматриваемые ниже алгоритмы всегда выдают верный результат, а случайным оказывается время работы.

Ожидаемое время — среднее по случайным решениям алгоритма на одном фиксированном входе. Верный результат получается в каждом запуске, но работа может различаться. Отдельный запуск всё ещё может оказаться неудачным.

Таким образом, мы не надеемся, что тесты окажутся случайными или «обычными». Источник случайности находится внутри алгоритма. В учебной модели будем считать выбор индекса равномерным; в программе его имитирует генератор псевдослучайных чисел.

Посмотрим, какую пользу даёт такой выбор. Возьмём сортировку, где элемент, выбранный опорным, определяет размеры следующих подзадач.

Сортировка слиянием сначала делила массив по индексам, а затем объединяла упорядоченные части. QuickSort делает основную работу до рекурсии: выбирает значение pivot и разбивает элементы на меньшие, равные и большие него.

Например, для [5, 2, 5, 8, 1] при pivot = 5 получим L = [2, 1], E = [5, 5], R = [8]. Любой элемент L должен стоять раньше любого элемента E, а E — раньше R. Поэтому достаточно отсортировать только L и R и соединить три части. Группа равных уже находится на своём месте.

quickSort(A):
    if length(A) <= 1: return A
    pivot = randomChoice(A)
    L = [x in A if x < pivot]
    E = [x in A if x == pivot]
    R = [x in A if x > pivot]
    return quickSort(L) + E + quickSort(R)

Разбиение массива длины n требует линейного прохода. Дальнейшая работа зависит от размеров частей. Если они близки к половинам, на каждом уровне суммарно обрабатывается O(n) элементов, а уровней O(log n). Если каждый раз отделяется только один элемент, размеры становятся n, n−1, n−2, … и сумма вырастает до Θ(n²).

В таблице разделены гарантия для самого плохого хода выполнения и ожидание при случайном выборе. Оценка для сбалансированных разбиений описывает, в частности, входы с различными ключами; при большом числе повторов трёхчастный вариант может закончить быстрее, вплоть до одного прохода на полностью одинаковом массиве.

Пример ниже намеренно создаёт отдельные списки для трёх частей: так хорошо видно устройство алгоритма. Это не реализация с постоянной дополнительной памятью. Сначала разберём выбор pivot, затем заменим создание списков перестановками внутри исходного массива.

def quick_sort(values: list[int], seed: int = 1) -> list[int]:
    def solve(a: list[int]) -> list[int]:
        nonlocal seed
        if len(a) < 2:
            return a.copy()
        seed = (seed * 1664525 + 1013904223) & 0xffffffff
        pivot = a[seed % len(a)]
        left, equal, right = [], [], []
        for x in a:
            if x < pivot: left.append(x)
            elif x > pivot: right.append(x)
            else: equal.append(x)
        return solve(left) + equal + solve(right)
    return solve(values)

print(quick_sort([7, 2, 9, 4, 2, 1]))

fn quick_sort(a: &[i64], seed: &mut u32) -> Vec<i64> {
    if a.len() < 2 { return a.to_vec(); }
    *seed = seed.wrapping_mul(1664525).wrapping_add(1013904223);
    let pivot = a[*seed as usize % a.len()];
    let (mut left, mut equal, mut right) = (Vec::new(), Vec::new(), Vec::new());
    for &x in a {
        if x < pivot { left.push(x); }
        else if x > pivot { right.push(x); }
        else { equal.push(x); }
    }
    let mut result = quick_sort(&left, seed);
    result.extend(equal);
    result.extend(quick_sort(&right, seed));
    result
}

fn main() {
    println!("{:?}", quick_sort(&[7, 2, 9, 4, 2, 1], &mut 1));
}

[1, 2, 2, 4, 7, 9]

QuickSort корректен при любом выборе pivot. Для оценки скорости осталось объяснить, почему случайный выбор обычно не позволяет дереву рекурсии вытянуться в длинную цепочку.

Опора около середины значения оставляет две небольшие части. Крайняя опора создаёт цепочку почти прежнего размера. Случайный индекс позволяет избежать систематически одного плохого выбора, но не делает каждое разбиение равным.

Для анализа сначала предположим, что все ключи различны, и расположим их мысленно по возрастанию. Опорный элемент из центральной трети оставляет с каждой стороны не больше примерно 2n/3 элементов. Назовём такое разбиение удачным: оно не обязано быть ровно пополам, достаточно отсечь постоянную долю.

Повторы требуют отдельного внимания. Если все значения равны, двухчастное разбиение может удалять из рассмотрения только один элемент за шаг. Разделение на < pivot, = pivot, > pivot сразу исключает всю группу равных и сохраняет прогресс.

С выбором опорного элемента разобрались. Теперь отделим математическую идею разбиения от способа её реализации: те же группы можно получить без создания трёх новых массивов.

Сначала сохраним уже понятные три группы без дополнительных списков. Возьмём pivot = 5. Слева будут меньшие, затем равные, посередине ещё неизвестные, справа большие. После каждого обмена все обработанные области должны оставаться правильными.

lt = i = 0
gt = len(a)
while i < gt:
    if a[i] < pivot:
        a[lt], a[i] = a[i], a[lt]
        lt += 1
        i += 1
    elif a[i] == pivot:
        i += 1
    else:
        gt -= 1
        a[i], a[gt] = a[gt], a[i]
        # a[i] ещё не проверен: i не увеличиваем

Теперь для сравнения рассмотрим двухчастный вариант с pivot в конце. В нём другой инвариант: равные не выделяются в отдельную готовую часть. На одинаковых элементах такой вариант может давать плохое сокращение. Не смешивайте его указатели i,j с lt,i,gt предыдущей реализации.

Разбиение можно выполнить обменами на полуинтервале A[l:r). Рассмотрим простой вариант: перенесём pivot в последнюю ячейку и будем просматривать остальные элементы слева направо.

Перед обработкой позиции j поддерживаем четыре области: A[l:i) содержит значения меньше pivot, A[i:j) — не меньше него, A[j:r−1) ещё не просмотрена, а A[r−1] хранит сам pivot. Если очередной элемент меньше pivot, меняем его с A[i] и увеличиваем i. В любом случае j продвигается вправо.

pivot = A[r−1]
i = l
for j = l .. r−2:
    if A[j] < pivot:
        swap(A[i], A[j]); i += 1
swap(A[i], A[r−1])
return i

После прохода неизвестная область пуста. Обмен A[i] с последним элементом ставит pivot на итоговую позицию: слева все значения меньше него, справа — не меньше. Части ещё не отсортированы, но уже известно, какую из них обрабатывать дальше.

Этот двухчастный вариант удобен для доказательства инварианта, однако множество равных значений может дать несбалансированную рекурсию. В примере Python и Rust ниже показано трёхчастное разбиение: оно дополнительно выделяет готовый блок равных. Само разбиение работает за O(n) времени и O(1) дополнительной памяти.

def partition(a: list[int], pivot: int) -> int:
    boundary = 0
    for j in range(len(a)):
        if a[j] < pivot:
            a[boundary], a[j] = a[j], a[boundary]
            boundary += 1
    return boundary

data = [7, 2, 9, 1, 5, 4]
boundary = partition(data, 5)
print(data)
print(boundary)

fn partition(a: &mut [i64], pivot: i64) -> usize {
    let mut boundary = 0;
    for j in 0..a.len() {
        if a[j] < pivot {
            a.swap(boundary, j);
            boundary += 1;
        }
    }
    boundary
}

fn main() {
    let mut data = [7, 2, 9, 1, 5, 4];
    let boundary = partition(&mut data, 5);
    println!("{:?}", data);
    println!("{}", boundary);
}

[2, 1, 4, 7, 5, 9]
3

Разбиение сообщает больше, чем только две группы: оно показывает, сколько элементов меньше pivot и сколько ему равны. Этой информации достаточно, чтобы найти элемент заданного ранга, продолжая лишь одну ветвь рекурсии.

def split3(a, pivot):
    left, equal, right = [], [], []
    for x in a:
        # Добавьте x ровно в одну группу.
        pass
    return [left, equal, right]

В рейтинге [7,2,9,4,4] нужен только третий результат по возрастанию — число 4 с индексом k = 2. Зачем полностью сортировать всех участников? Разбиение уже показывает, какие места занимают группы; нужную группу достаточно продолжить одну.

k-я порядковая статистика (Order statistic) — Элемент с индексом k в мысленно отсортированном массиве; индексация с нуля.

Индекс k считаем с нуля, поэтому минимум имеет ранг 0, максимум — n−1. Для [7, 2, 9, 4, 4] статистика с k = 2 равна 4. При чётной длине под медианой нужно заранее договориться понимать одну из двух центральных статистик или их среднее.

Выполним такое же разбиение L, E, R, как в QuickSort. Если k < |L|, ответ лежит слева. Если |L| ≤ k < |L|+|E|, ответ равен pivot. Иначе переходим вправо и уменьшаем локальный ранг на |L|+|E|.

select(A, k):
    pivot = randomChoice(A)
    L, E, R = split3(A, pivot)
    if k < len(L): return select(L, k)
    if k < len(L) + len(E): return pivot
    return select(R, k − len(L) − len(E))

QuickSelect продолжает только одну ветвь. При удачных сокращениях объём работы складывается как n + 2n/3 + (2/3)²n + … = O(n). Ожидаемое число попыток до очередного удачного сокращения постоянно, поэтому при случайном pivot ожидаемое время линейно. Цепочка крайне неудачных выборов всё ещё даёт Θ(n²).

QuickSort сортирует обе внешние части, QuickSelect продолжает только одну; равные опоре сразу дают готовый диапазон рангов. В основном маршруте дальше сравним, какой метод нужен вашей задаче. Детерминированный выбор и доказательство нижней границы доступны отдельно.

def kth(a, k):
	# Напишите решение здесь
	pass

Сначала спросите: нужен весь порядок или один ранг? Затем: достаточно среднего по запускам или нужна гарантия худшего случая? Для полной сортировки дополнительно проверьте устойчивость и память.

Общая операция у рассмотренных методов — разбиение относительно pivot. Различаются две вещи: сколько частей мы продолжаем обрабатывать и как выбираем опорный элемент. Эти решения определяют и результат, и оценку времени.

Если нужен полный порядок, QuickSort обрабатывает обе внешние части. Если нужен только один ранг, QuickSelect оставляет одну. Если необходима линейная гарантия для любого входа, медиана медиан обеспечивает достаточно сбалансированный шаг без генератора случайных чисел.

При чтении кода также различайте память разбиения и память всей программы. Обмены могут требовать O(1) дополнительных ячеек, но рекурсивные вызовы занимают стек. Примеры со списками L, E, R явно выделяют новые массивы и служат понятной реализацией идеи, а не обещанием минимального расхода памяти.

Теперь вы умеете выполнять трёхчастное разбиение, выбирать одну ветвь QuickSelect и различать ожидаемое и худшее время. В лекции 04 используем сами значения небольших целых ключей: вместо сравнений они станут индексами счётчиков.

Справочник собирает определения из разобранных разделов. Используйте поиск, если нужно восстановить термин; затем переходите к оценке ограничений и задачам для самостоятельного решения.

Общий справочник всех лекций ↗

Найдено: 13 из 13

При выборе между разобранными методами сначала определите, нужен ли полный порядок или только один ранг. Для n ≤ 200 000 сортировка с ожидаемой O(n log n) и выбор с ожидаемой O(n) решают разные объёмы работы; O(n²) на неудачном разбиении означает десятки миллиардов просмотров.

Ожидаемое время и максимальная глубина

Случайный pivot даёт хорошее математическое ожидание для фиксированного входа, но не исключает долгую цепочку. При требовании жёсткой гарантии рассматривайте heapsort, merge sort, детерминированный выбор или гибрид. Сортировка меньшей части рекурсивно и продолжение большей циклом ограничивает глубину стека, но само по себе не устраняет квадратичное число сравнений.

Считаем память реализации

Выделение левой и правой частей проще in-place кода, но копирование и рекурсия расходуют память. На цепочке очень несбалансированных разбиений накопленные копии могут потребовать O(n²) пикового хранения. Для воспроизводимых тестов фиксируйте seed; сравнивайте вывод с эталонной сортировкой, а не с одной удачной трассировкой.

При частых повторах используйте трёхчастное разбиение. На массиве из одинаковых чисел оно завершает обработку за один линейный проход. Уточните, что k-й элемент считается с кратностями: в [1, 1, 8] второй элемент равен 1, а не 8.

Что проверить перед отправкой

• Пустой вход и недопустимый k обрабатываются контрактом.
• Прямой и обратный порядок, все равные элементы, много повторов.
• Индекс k корректно пересчитывается при переходе в правую часть.
• Для t тестов оценивается сумма размеров и стоимостей, а не один средний запуск.

def partition_parity(a):
    # Разделите одним проходом по предикату x % 2 == 0.
    pass

def split3(a, pivot):
    left, equal, right = [], [], []
    for x in a:
        # Добавьте x ровно в одну группу.
        pass
    return [left, equal, right]

def kth(a, k):
	# Напишите решение здесь
	pass

Примените разобранные приёмы самостоятельно. Для каждой задачи сначала сформулируйте требования к ответу и предложите простое решение. Затем подставьте максимальные ограничения, оцените время и память и решите, какое улучшение требуется. Подсказки с идеей и оценкой раскрываются отдельно.

Уровни задают порядок практики в курсе, а не единую шкалу платформ. Если уровень отличается от отметки LeetCode, это указано в карточке. Для Codeforces используется оценка курса.