Блочная сортировка: линия в среднем на равномерных данных

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

Как думаешь, можно ли без подсчёта сортировать дробные числа за линию

Сортировка подсчётом и поразрядная требуют целых ключей из обозримого диапазона. А что, если ключи - дробные числа из [0, 1): доли, вероятности, нормированные оценки? Их значений бесконечно много, массив счётчиков не заведёшь.

Прежде чем читать дальше, попробуй угадать: если миллион чисел из [0, 1) разбросан равномерно, сколько из них в среднем попадёт в отрезок [0.5, 0.500001) длиной в одну миллионную? И что из этого следует для сортировки?

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

Сортировка писем на почте по индексам. Сортировщик не сравнивает письма друг с другом - он бросает каждое в ячейку стеллажа по первым цифрам индекса. Если письма приходят со всей страны равномерно, в каждой ячейке их несколько, и навести порядок внутри ячейки - секундное дело. А если все письма в этот день идут в один город - одна ячейка переполнена, остальные пусты, и сортировщик снова перебирает огромную пачку вручную. Стеллаж работает, пока письма распределены по ячейкам ровно.

Механизм: корзины, вставки, склейка

вход: a[0..n−1], все числа в [0, 1)

1. завести n пустых корзин
2. каждое x положить в корзину ⌊x · n⌋        Θ(n)
3. каждую корзину отсортировать вставками    сумма по корзинам
4. выписать корзины по порядку номеров       Θ(n)

Склейка корзин по порядку даёт отсортированный массив, потому что корзина i содержит числа из [i/n, (i+1)/n): всё, что в корзине i, меньше всего, что в корзине i+1. Сравнения нужны только внутри корзины.

Сколько стоит шаг 3? Сортировка вставками делает столько сдвигов, сколько в корзине инверсий - пар, стоящих в неправильном порядке. Инверсия возможна только между числами из ОДНОЙ корзины. Считаем пары:

пар всего:                          n·(n−1)/2
вероятность, что пара в одной корзине:  1/n
    (при равномерных данных второе число попадает
     в корзину первого с вероятностью 1/n)
пар в одной корзине в среднем:      n·(n−1)/2 · 1/n = (n−1)/2
из них инверсий - половина:         (n−1)/4

То есть в среднем меньше одной инверсии на элемент, и шаг 3 стоит Θ(n). Вся сортировка - Θ(n) в среднем.

Правило

Блочная сортировка кладёт x ∈ [0, 1) в корзину ⌊x·n⌋, сортирует корзины вставками и склеивает по порядку. На равномерных данных каждая пара попадает в одну корзину с вероятностью 1/n, поэтому пар-соседей по корзине в среднем (n−1)/2, инверсий - (n−1)/4, и сортировка стоит Θ(n) в среднем. Это среднее по ДАННЫМ, а не гарантия: на скученных данных корзины переполняются, и худший случай - Θ(n²). Граница n·log n не нарушена: элементы раскладываются по значению, а сравнения идут лишь внутри корзин.

Разбор: десять чисел по десяти корзинам

вход: 0.78  0.17  0.39  0.26  0.72  0.94  0.21  0.12  0.23  0.68
n = 10, корзина = первая цифра после запятой

корзина 1: 0.17 0.12   → вставками: 0.12 0.17   (1 сдвиг)
корзина 2: 0.26 0.21 0.23 → 0.21 0.23 0.26      (2 сдвига)
корзина 3: 0.39
корзина 6: 0.68
корзина 7: 0.78 0.72   → 0.72 0.78              (1 сдвиг)
корзина 9: 0.94
остальные пусты

склейка: 0.12 0.17 0.21 0.23 0.26 0.39 0.68 0.72 0.78 0.94

Четыре сдвига на десять чисел. Формула обещала в среднем (10−1)/4 = 2.25 - здесь вышло чуть больше, потому что три числа случайно легли в корзину 2. Ровно так выглядит «в среднем»: отдельный вход отклоняется, но не далеко.

Разбор: равномерные данные против скученных

Программа сортирует блочной сортировкой n равномерных чисел и n чисел вида x⁸ - они тоже из [0, 1), но сгрудились у нуля. Считаем сдвиги сортировки вставками внутри корзин.

import random


def bucket_sort(a):
    n = len(a)
    buckets = [[] for _ in range(n)]
    for x in a:
        buckets[int(x * n)].append(x)
    shifts = 0
    out = []
    for b in buckets:
        for i in range(1, len(b)):          # вставками внутри корзины
            x, j = b[i], i - 1
            while j >= 0 and b[j] > x:
                b[j + 1] = b[j]
                j -= 1
                shifts += 1
            b[j + 1] = x
        out.extend(b)
    return out, shifts


rng = random.Random(1)
for n in (2000, 4000, 8000, 16000):
    ravn = [rng.random() for _ in range(n)]
    kosye = [rng.random() ** 8 for _ in range(n)]
    r1, s1 = bucket_sort(ravn)
    r2, s2 = bucket_sort(kosye)
    assert r1 == sorted(ravn) and r2 == sorted(kosye)
    print(f"n={n}: равномерные {s1} сдвигов, перекошенные {s2}")

n=2000: равномерные 475 сдвигов, перекошенные 154215
n=4000: равномерные 1008 сдвигов, перекошенные 502168
n=8000: равномерные 1974 сдвигов, перекошенные 1703677
n=16000: равномерные 3945 сдвигов, перекошенные 5586347

У равномерных сдвигов почти ровно n/4, как и обещал счёт пар: 2000/4 = 500, 16000/4 = 4000. При удвоении n они удваиваются - линия. У скученных при каждом удвоении n сдвигов становится больше в 3.3-3.4 раза, то есть рост почти квадратичный: половина чисел x⁸ меньше 0.004, и при n = 16000 все они толпятся в первых 63 корзинах из 16000.

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

Блочную сортировку применяют к данным, не спросив, как они распределены, - и получают квадрат там, где ждали линию. Симптом узнаваемый: на тестовых случайных числах всё летает, на настоящих данных (суммы платежей, время отклика, размеры файлов - у всех них длинный хвост и толпа у малых значений) сортировка тормозит в сотни раз. Вторая ошибка - число корзин меньше n: при k корзинах в каждой окажется около n/k чисел, и вставки внутри стоят n²/k - при k = 10 это просто сортировка вставками, ускоренная в десять раз. Третья - забыть, что ⌊x·n⌋ при x = 1.0 даёт корзину n, которой нет: интервал должен быть полуоткрытым.

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

Чистая блочная сортировка встречается редко, а её идея - постоянно. Внешняя сортировка больших файлов и параллельная сортировка на многих машинах начинаются с того же шага: разбить диапазон ключей на корзины и отправить каждую корзину на свой диск или свою машину. Там корзины выбирают не равными по ширине, а по ВЫБОРКЕ из данных - так, чтобы в каждую попало примерно поровну, и скученность перестаёт быть проблемой. Та же мысль стоит за гистограммой в базе данных: планировщик запросов делит значения столбца на корзины равной заполненности, а не равной ширины. Когда видишь «разбить на диапазоны и обработать каждый отдельно», первым делом спроси, как будут распределены данные по диапазонам.

Теперь сам

n = 1000 чисел из [0, 1), но все они лежат в [0, 0.01) и внутри этого отрезка распределены равномерно. Сколько корзин из тысячи окажутся непустыми и сколько в среднем инверсий получит сортировка вставками внутри корзин? Как починить, не меняя алгоритм?