Сортировка без сравнений (подсчётом / поразрядная)

Сортировка без сравнений (подсчётом / поразрядная): как это работает?

Сортировке подсчётом нужны ключи из известного узкого диапазона. Заведите по счётчику на каждый возможный ключ.

Пройдите вход один раз и посчитайте каждый ключ. Теперь известно, сколько каких значений.

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

Пройдите вход второй раз и положите каждый элемент на его позицию. Ничего ни разу не сравнивалось.

Поразрядная сортировка применяет ту же идею по одному разряду. Она начинает с младшего разряда.

Каждый проход по разряду обязан быть устойчивым. Неустойчивый проход отменяет все предыдущие.

1. счётчики = [1, 1, 2]Сортируем [2, 0, 2, 1]. Один ноль, одна единица, две двойки.
2. старты = [0, 1, 2]Накопленные суммы дают каждому ключу его первую ячейку.
3. [0, _, _, _]Ноль ложится в ячейку 0. Его старт сдвигается на единицу.
4. [0, 1, 2, _]Единица занимает ячейку 1, первая двойка ячейку 2.
5. [0, 1, 2, 2]Вторая двойка занимает ячейку 3. Ни одного сравнения не было.

function countingSort(arr, maxVal) {
    const counts = new Array(maxVal + 1).fill(0);
    for (const x of arr) counts[x]++;
    const out = [];
    for (let v = 0; v <= maxVal; v++) {
        while (counts[v]-- > 0) out.push(v);
    }
    return out;
}

Сортировка без сравнений (подсчётом / поразрядная): разбор примера

K самых частых значений

Верните k значений, которые встречаются чаще всего.

Сортировка счётчиков стоит n log n, а полный порядок задаче не нужен.

Посчитайте все значения словарём. Счётчик не может превысить длину массива.

Используйте сам счётчик как индекс в списке корзин. Читайте корзины с конца.

function topKFrequent(nums, k) {
    const count = new Map();
    for (const x of nums) count.set(x, (count.get(x) ?? 0) + 1);

    // bucket i holds every value that appeared exactly i times
    const buckets = Array.from({ length: nums.length + 1 }, () => []);
    for (const [value, c] of count) buckets[c].push(value);

    const answer = [];
    for (let c = buckets.length - 1; c >= 1 && answer.length < k; c--) {
        for (const value of buckets[c]) {
            answer.push(value);
            if (answer.length === k) break;
        }
    }

    return answer;
}

Сортировка без сравнений (подсчётом / поразрядная): когда применять?

Эти формулировки в условии ведут сюда:

• •ключи — целые числа в небольшом известном диапазоне
• •сортировка возрастов, оценок или ограниченных счётчиков
• •нужна O(n), а сравнения — узкое место
• •сортировка по разрядам или ключу фиксированной ширины
• •n большое, но диапазон значений намного меньше n

Сортировка без сравнений (подсчётом / поразрядная): с чем путают?

• Быстрая сортировка (merge / quick) (Fast sort (merge / quick)): Никакая сортировка сравнением не быстрее n log n. Чтение ключа обходит этот предел целиком.
• Хеш-множество / словарь (Hash set / map): Словарь тоже считает значения, но порядка не хранит. Сортировка подсчётом делает значение индексом.
• Сортировка с пользовательским компаратором (Sort with a custom comparator): Компаратор описывает порядок между двумя элементами. Подсчёт вообще не смотрит на пары.
• Элементарные сортировки (выбором, пузырьком, вставками) (Elementary sorts (selection, bubble, insertion)): Те сравнивают соседей и стоят n в квадрате. Подсчёт линеен, если диапазон позволяет.

Сортировка без сравнений (подсчётом / поразрядная): частые ошибки

• Берут её на огромном диапазоне ключей

  Счётчик на каждый ключ означает память размером с диапазон. Значения до 1e9 делают это невозможным.

• Неустойчивый проход внутри поразрядной

  Каждый проход по разряду обязан сохранить прошлый порядок. Иначе ранняя работа пропадает.

• Забывают про отрицательные значения

  Индекс массива не бывает отрицательным. Сдвиньте все ключи на минимум.

• Считают дробные числа или строки

  Ключ обязан быть ограниченным целым. Всё остальное требует сортировки сравнением.

Сортировка без сравнений (подсчётом / поразрядная): задачи с собеседований

• Сортировка небольших целых: По счётчику на значение, потом чтение по порядку.
• Сортировка цветов: Возможных ключей три, значит и счётчика три.
• K самых частых элементов: Сам счётчик становится индексом корзины.
• Индекс Хирша: Счётчики цитирований, ограниченные числом работ.
• Максимальный разрыв: Поразрядная сортировка и делает линейное решение возможным.
• Относительная сортировка массива: Подсчёт с порядком, заданным другим списком.
• Сортировка символов по частоте: Корзины по числу вхождений буквы.

Сортировка без сравнений (подсчётом / поразрядная): сложность по времени и памяти

O(n)

n значений с ключами меньше k дают O(n + k). Поразрядная стоит O(d умножить на n) при d разрядах.