Сортировки без сравнений и сортировочные сети

Например, баллы участников лежат от 0 до 100. Вместо сравнений каждой пары кандидатов заведём 101 счётчик: в ячейке с индексом s будем хранить число участников с баллом s. Одним проходом по данным узнаем все частоты, затем просмотрим значения по возрастанию.

Пусть 200 000 участников получили баллы 0…100: достаточно 101 счётчика. При том же числе участников, но ключах 0…10⁹, таблица уже огромна. Выбор зависит и от числа записей, и от диапазона значений.

Ключ (Key) — Значение, по которому упорядочивают объект; сам объект может содержать и другие данные.

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

Обозначим число элементов через n, а размер диапазона ключей — через m: 0 ≤ key < m. В оценке появятся оба параметра. Это честная плата за более сильное предположение о входе, а не опровержение границы из предыдущей лекции.

При выборе алгоритма проверяйте не только длину массива, но и диапазон значений. При n = 1000 и m = 10⁹ инициализация счётчиков уже дороже обычной сортировки. Сжатие координат обычно требует предварительно упорядочить разные ключи, поэтому само по себе не делает весь процесс линейным.

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

Пусть вход равен [3, 1, 3, 0, 1], а m = 4. Частоты будут [1, 2, 0, 2]. Выпишем 0 один раз, 1 два раза, 2 ни разу и 3 два раза — получим [0, 1, 1, 3, 3].

Создадим массив count из m нулей. Для каждого входного x увеличим count[x]. После этого исходный порядок уже не важен: частоты полностью описывают, сколько экземпляров каждого числа должно попасть в ответ.

count = [0] * m
for x in A: count[x] += 1
out = []
for key = 0 .. m−1:
    repeat count[key] times: out.push(key)
return out

Инициализация счётчиков и просмотр диапазона требуют Θ(m), чтение входа и запись результата — Θ(n). Поэтому время равно Θ(n + m). В показанном варианте отдельно хранятся счётчики и выходной массив.

Отрицательные ключи тоже допустимы, если диапазон мал: используйте индекс x−minKey и m = maxKey−minKey+1. Препятствие — большой размах значений, а не знак числа.

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

Пусть вместо чисел сортируются записи (балл, имя). Для входа [(2, Анна), (1, Борис), (2, Вера)] хотим получить [(1, Борис), (2, Анна), (2, Вера)]. Помимо порядка баллов, сохраним порядок Анны и Веры, у которых ключи совпадают.

Устойчивая сортировка (Stable sort) — Не меняет относительный порядок объектов с равными ключами.

Из частот вычислим, где начинается каждая группа в выходном массиве. Перед группой ключа k стоят все элементы с меньшими ключами, поэтому её начало равно сумме count[0] + … + count[k−1]. Эти суммы называются префиксными.

Для частот [1,2,0,2] группа нулей начинается в 0, единиц — в 1, двоек и троек — в 3. Двоек нет, поэтому их пустая группа не занимает места. Сначала вычислите эти адреса сами.

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

count[key] = число объектов с данным ключом
start[0] = 0
for k = 1 .. m−1: start[k] = start[k−1] + count[k−1]
for object in A (слева направо):
    k = object.key
    out[start[k]] = object
    start[k] += 1

На примере с именами две записи с ключом 2 попадут в соседние ячейки в исходном порядке. В коде Python и Rust ниже переносится вся запись, а не только ключ. Можно реализовать и обход справа налево с концами групп, но направление обхода и правило изменения указателя должны согласовываться.

def stable_count(records: list[tuple[int, str]], m: int):
    assert m >= 0 and all(0 <= key < m for key, _ in records)
    count = [0] * m
    for key, _ in records:
        count[key] += 1
    start = [0] * m
    for key in range(1, m):
        start[key] = start[key - 1] + count[key - 1]
    out = [(0, "")] * len(records)
    for key, label in records:
        out[start[key]] = (key, label)
        start[key] += 1
    return out

data = [(2,"A"), (0,"B"), (2,"C"), (1,"D"), (0,"E"), (2,"F"), (1,"G")]
print(" ".join(label for _, label in stable_count(data, 3)))

fn stable_count(records: &[(usize, char)], m: usize) -> Vec<(usize,char)> {
    assert!(records.iter().all(|&(key,_)| key < m));
    let mut count = vec![0; m];
    for &(key,_) in records { count[key] += 1; }
    let mut start = vec![0; m];
    for key in 1..m { start[key] = start[key-1] + count[key-1]; }
    let mut out = vec![(0,' '); records.len()];
    for &(key,label) in records {
        out[start[key]] = (key,label);
        start[key] += 1;
    }
    out
}

fn main() {
    let data = [(2,'A'),(0,'B'),(2,'C'),(1,'D'),(0,'E'),(2,'F'),(1,'G')];
    let names: Vec<String> = stable_count(&data,3).iter()
        .map(|&(_,label)| label.to_string()).collect();
    println!("{}", names.join(" "));
}

B E D G A C F

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

def stable_by_key(records):
	# Напишите решение здесь
	pass

Например, для [21, 13, 12, 23] устойчивый проход по единицам даст [21, 12, 13, 23]. Затем проход по десяткам даст [12, 13, 21, 23]. Внутри одинаковой десятки сохраняется порядок по единицам, установленный первым проходом.

Если диапазон всего числа слишком велик для счётчиков, рассмотрим его цифры по отдельности. Запишем ключи в системе с основанием m: каждая цифра уже лежит в небольшом диапазоне 0…m−1. Схема LSD начинает с младшей цифры и движется к старшим.

for d = 0 .. k−1:
    A = stableCountingSort(A, key=(x // m**d) % m)
return A

Инвариант после j проходов: числа упорядочены по j младшим разрядам. Следующий устойчивый проход группирует их по новой цифре и сохраняет внутри группы порядок предыдущих разрядов. После обработки всех k цифр получаем порядок по всему ключу.

Цена одного прохода — Θ(n + m), а число проходов — k. Если ключ имеет w бит и за раз берём b бит, то m = 2ᵇ, k = ⌈w/b⌉. Большое основание уменьшает число проходов, но увеличивает таблицу счётчиков. Для 32-битных беззнаковых ключей байтовый вариант использует четыре прохода и 256 счётчиков.

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

def radix_sort(values: list[int]) -> list[int]:
    assert all(0 <= x < 2**32 for x in values)
    a = values.copy()
    for shift in range(0, 32, 8):
        count = [0] * 256
        for x in a: count[(x >> shift) & 255] += 1
        start = [0] * 256
        for d in range(1, 256): start[d] = start[d-1] + count[d-1]
        out = [0] * len(a)
        for x in a:
            d = (x >> shift) & 255
            out[start[d]] = x
            start[d] += 1
        a = out
    return a

print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))

fn radix_sort(values: &[u32]) -> Vec<u32> {
    let mut a = values.to_vec();
    for shift in (0..32).step_by(8) {
        let mut count = [0_usize; 256];
        for &x in &a { count[((x >> shift) & 255) as usize] += 1; }
        let mut start = [0_usize; 256];
        for d in 1..256 { start[d] = start[d-1] + count[d-1]; }
        let mut out = vec![0; a.len()];
        for &x in &a {
            let d = ((x >> shift) & 255) as usize;
            out[start[d]] = x;
            start[d] += 1;
        }
        a = out;
    }
    a
}

fn main() {
    println!("{:?}",radix_sort(&[170,45,75,90,802,24,2,66]));
}

[2, 24, 45, 66, 75, 90, 170, 802]

Основной маршрут завершён: вы умеете считать частоты, устойчиво распределять записи и сохранять младшие разряды между проходами. Перейдите к ограничениям и практике. Следующие четыре главы — дополнительный модуль «Параллельные алгоритмы» с сохранёнными моделями сетей.

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

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

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

Применим полученные оценки к максимальному входу. Для целочисленных сортировок отдельно запишите n, диапазон m и число разрядов k. Без этих параметров фраза «линейная сортировка» неполна: O(n + m) может оказаться хуже O(n log n).

Сравниваем длину массива и диапазон ключей

• n = 200 000 и ключи 0…100: 101 счётчик, время O(n + 101), небольшой дополнительный диапазон.
• n = 200 000 и ключи 0…10⁹: массив из миллиарда счётчиков u32 занимает около 4 ГБ полезных данных. Лучше анализировать radix sort или сортировку сравнением.
• При u32 и основании 256 требуется четыре прохода. Для n = 10⁶ один буфер ключей занимает 4 МБ, вход и выход — около 8 МБ без прочих данных.

Разрядность и стоимость индексации

Значение Python int не ограничено 32 битами. В приведённом radix-примере контракт явно ограничивает диапазон u32, иначе четырёх проходов недостаточно. Для строк переменной длины нужно определить порядок символов, обработку конца строки и длину ключа; переносить числовой шаблон без изменений нельзя.

def counting_sort(a, m):
    # Посчитайте частоты, затем восстановите числа по возрастанию ключей.
    pass

def stable_by_key(records):
	# Напишите решение здесь
	pass

def byte_at(x, i):
	# Напишите решение здесь
	pass

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

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