Быстрая сортировка в ожидании: 1,39 · n · log₂ n на любом входе

Если ты объяснишь, когда два элемента сравниваются, выведешь 2/(d + 1) и скажешь, какое условие доказательства нарушает массив из одинаковых чисел, - листай до «Теперь сам».

Как думаешь, сравнит ли сортировка наименьший элемент с наибольшим

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

Попробуй угадать до чтения: с какой вероятностью за всю сортировку эти два числа хоть раз будут сравнены друг с другом - почти наверняка, в половине случаев или почти никогда? Ответ - 2/1000. А два числа, соседние по величине, сравниваются всегда. В разделе про сортировки оценка «в среднем n · log n» была принята рассуждением о хороших и плохих разбиениях; здесь она выводится точно, вместе с множителем.

На что это похоже

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

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

Механизм: кто с кем сравнивается

Разбиение сравнивает опорный со всеми остальными элементами своего участка и больше никого ни с кем. Ни одна пара не сравнивается дважды: опорный после разбиения встаёт на место и в дальнейшем не участвует. Значит, число сравнений - это число пар, которые были сравнены, и считать его можно индикаторами: по одному на пару.

Назовём элементы по порядку величины: z₁ < z₂ < … < zₙ. Возьмём пару zᵢ и zⱼ и все элементы между ними: всего j − i + 1 штук.

z₁ … zᵢ₋₁  [ zᵢ  zᵢ₊₁  …  zⱼ₋₁  zⱼ ]  zⱼ₊₁ … zₙ
             └──── j − i + 1 штук ───┘

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

• если это zᵢ или zⱼ, он сравнивается со всеми в своём участке, включая второй элемент пары;
• если это кто-то между ними, zᵢ уходит влево, zⱼ вправо, и они не встретятся никогда.

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

P(zᵢ и zⱼ сравниваются) = 2 / (j − i + 1)

Теперь сумма по парам. Обозначим d = j − i; пар с данным d ровно n − d.

E[сравнений] = сумма по d от 1 до n − 1:  (n − d) · 2 / (d + 1)  =  2(n + 1)·Hₙ − 4n

Последнее равенство получается, если записать n − d как (n + 1) − (d + 1): слагаемое распадается на 2(n + 1) / (d + 1) и −2; первые дают 2(n + 1) · (Hₙ − 1), вторые - −2(n − 1).

Hₙ ≈ ln n + 0,577, поэтому главная часть - 2n · ln n. В двоичных логарифмах ln n = 0,693 · log₂ n, и получается 1,39 · n · log₂ n. Логарифм возник как сумма долей 2/(d + 1): далёкие по величине элементы сравниваются редко, и вклад пар убывает как гармонический ряд.

Правило

Быстрая сортировка, выбирающая опорный равновероятно из участка, на любом входе из n разных элементов делает в среднем 2(n + 1)Hₙ − 4n ≈ 1,39 · n · log₂ n сравнений. Элементы, которые в отсортированном порядке стоят на местах i < j, сравниваются с вероятностью 2 / (j − i + 1). Ожидание берётся по случайным выборам алгоритма; входа, на котором оно хуже, не существует.

Разбор: формула и пять запусков на отсортированном входе

Сортировка написана с явным стеком вместо рекурсии, чтобы не упираться в предел глубины вызовов. Разбиение - простое: опорный переставляется в конец участка, указатель mesto отделяет элементы, меньшие опорного. Вход - числа от 0 до 499 по возрастанию, самый неудобный для сортировки с неслучайным опорным.

import random

def sortirovat(a, sluchajnyj):
    sravnenij = 0
    stek = [[0, len(a) - 1]]
    while len(stek) > 0:
        granicy = stek.pop()
        levo = granicy[0]
        pravo = granicy[1]
        if levo >= pravo:
            continue
        if sluchajnyj:
            p = random.randint(levo, pravo)
            t = a[p]
            a[p] = a[pravo]
            a[pravo] = t
        opornyj = a[pravo]
        mesto = levo
        for i in range(levo, pravo):
            sravnenij = sravnenij + 1
            if a[i] < opornyj:
                t = a[i]
                a[i] = a[mesto]
                a[mesto] = t
                mesto = mesto + 1
        t = a[mesto]
        a[mesto] = a[pravo]
        a[pravo] = t
        stek.append([levo, mesto - 1])
        stek.append([mesto + 1, pravo])
    return sravnenij

n = 500
garm = 0
for i in range(1, n + 1):
    garm = garm + 1 / i
print(round(2 * (n + 1) * garm - 4 * n))

random.seed(33)
schet = []
for opyt in range(5):
    schet.append(sortirovat(list(range(n)), True))
print(schet, round(sum(schet) / 5))

4806
[4741, 5091, 4714, 5055, 4574] 4835

Формула даёт 4806, пять запусков - от 4574 до 5091, в среднем 4835. Разброс между запусками - в пределах шести процентов. Это не случайность выборки из пяти: известно, что стандартное отклонение числа сравнений близко к 0,65 · n, то есть для 500 элементов около 325 при среднем 4806. Число сравнений растёт как n · log n, а его разброс только как n, поэтому на больших массивах время рандомизированной сортировки почти не отличается от среднего.

Для сравнения: нижняя граница для любой сортировки сравнениями - log₂ n!, для n = 500 это 3767. Быстрая сортировка платит сверх неё около 28% при n = 500 и до 39% на очень больших n.

Разбор: тот же код без монетки, и вход, который ломает доказательство

Параметр sluchajnyj выключен: опорным всегда берётся последний элемент участка. Вход прежний, отсортированный, только короче - 250 элементов, чтобы уложиться в шаги.

def sortirovat(a):
    sravnenij = 0
    stek = [[0, len(a) - 1]]
    while len(stek) > 0:
        granicy = stek.pop()
        levo = granicy[0]
        pravo = granicy[1]
        if levo >= pravo:
            continue
        opornyj = a[pravo]
        mesto = levo
        for i in range(levo, pravo):
            sravnenij = sravnenij + 1
            if a[i] < opornyj:
                t = a[i]
                a[i] = a[mesto]
                a[mesto] = t
                mesto = mesto + 1
        t = a[mesto]
        a[mesto] = a[pravo]
        a[pravo] = t
        stek.append([levo, mesto - 1])
        stek.append([mesto + 1, pravo])
    return sravnenij

n = 250
print(sortirovat(list(range(n))), n * (n - 1) // 2)

31125 31125

Ровно n(n − 1) / 2: каждый опорный оказывается наибольшим, и участок уменьшается на один элемент. Со случайным опорным для 250 элементов ожидание - 2 · 251 · H₂₅₀ − 1000 ≈ 2063, в пятнадцать раз меньше. В терминах пар: без монетки сравнивается каждая пара, с монеткой - только пары, близкие по величине.

Теперь граница доказательства. В нём стояло слово «разных». Пусть массив состоит из тысячи одинаковых чисел. Условие a[i] < opornyj всегда ложно, все элементы остаются по одну сторону, участок уменьшается на один - и случайный выбор опорного не помогает, потому что все кандидаты одинаковы. Сравнений 1000 · 999 / 2 = 499 500 при любых монетках. Рассуждение про «первого опорного из группы между zᵢ и zⱼ» опиралось на то, что опорный из середины разводит пару в разные стороны; равные элементы он не разводит.

Лечится разбиением на три части: меньшие опорного, равные ему и большие. Равные опорному сразу стоят на своих местах и в рекурсию не идут. На массиве из одинаковых чисел такая сортировка заканчивает за один проход.

Что ломается без этого

Случайный опорный с известным зерном. Гарантия «плохого входа нет» держится на том, что автор входа не знает монеток. Если генератор засеян постоянным числом, а код открыт, злоумышленник прогонит алгоритм у себя и построит вход, на котором именно эти монетки дают квадрат.

Детерминированная «умная» эвристика вместо монетки. Медиана из трёх - первого, среднего и последнего элемента - убирает квадрат на отсортированном входе, но не убирает совсем: для любого правила, которое смотрит на несколько заранее известных мест, существует вход, дающий квадрат, и его можно построить автоматически, подсовывая сортировке ответы на сравнения. Без случайности квадрат исключает только точная медиана участка, найденная линейным алгоритмом выбора, - но она делает каждый уровень в несколько раз дороже.

Много одинаковых ключей. Сортировка столбца «статус заказа» с пятью разными значениями на миллион строк - ровно случай из разбора. Без трёхчастного разбиения она квадратична и с монеткой.

Среднее по входам вместо среднего по монеткам. «Данные у нас случайные, значит быстрая сортировка с первым элементом в роли опорного в среднем быстрая» - это обещание про данные. Журнал, отсортированный по времени, его нарушает.

Зачем это в работе

У защиты от худшего случая два пути, и библиотеки выбирают между ними. Первый - монетка: ожидаемое время хорошее на любом входе. Второй - страховка: неслучайный выбор опорного плюс слежение за глубиной рекурсии и переход на пирамидальную сортировку, если разбиения идут плохо. Так устроены introsort в стандартной библиотеке C++ и pdqsort, на котором построена сортировка в Go, а до 2024 года была построена и нестабильная сортировка в Rust. Страховка даёт твёрдые O(n · log n) в худшем случае, чего монетка обещать не может, и не требует источника случайности.

Монетка остаётся там, где страховки нет или она дорога: быстрый выбор k-го элемента, случайные приоритеты в декартовом дереве, случайный порядок вставки при построении структур вычислительной геометрии.

А сам способ анализа - «индикатор на пару, вероятность из симметрии» - переносится дословно. Средняя глубина узла в случайном дереве поиска и в декартовом дереве, число сравнений быстрого выбора считаются тем же рассуждением о том, кто из группы был выбран первым.

Теперь сам

1. Сортируют 100 разных чисел. С какой вероятностью наименьшее будет сравнено с наибольшим?
2. С какой вероятностью будут сравнены два числа, соседние по величине?
3. Найди ожидаемое число сравнений для трёх разных элементов, сложив вероятности по трём парам. Сверь с формулой 2(n + 1)Hₙ − 4n.
4. Оцени ожидаемое число сравнений для миллиона элементов; log₂ 10⁶ ≈ 20.
5. Массив состоит из 1000 нулей и 1000 единиц в случайном порядке. Чем плохо простое разбиение из урока и что изменит трёхчастное?