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

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

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

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

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

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

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

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

Источники: Википедия: Сортировка подсчётом, Википедия: Поразрядная сортировка

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;
}

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

def counting_sort(arr, max_val):
    counts = [0] * (max_val + 1)
    for x in arr:
        counts[x] += 1
    out = []
    for v, c in enumerate(counts):
        out.extend([v] * c)
    return out

function countingSort(array $arr, int $maxVal): array {
    $counts = array_fill(0, $maxVal + 1, 0);
    foreach ($arr as $x) $counts[$x]++;
    $out = [];
    for ($v = 0; $v <= $maxVal; $v++) {
        for ($c = $counts[$v]; $c > 0; $c--) $out[] = $v;
    }
    return $out;
}

    public static int[] countingSort(int[] arr, int maxVal) {
        int[] counts = new int[maxVal + 1];
        for (int x : arr) counts[x]++;
        int[] out = new int[arr.length];
        int k = 0;
        for (int v = 0; v <= maxVal; v++) {
            while (counts[v]-- > 0) out[k++] = v;
        }
        return out;
    }

    public static int[] CountingSort(int[] arr, int maxVal) {
        var counts = new int[maxVal + 1];
        foreach (int x in arr) counts[x]++;
        var outArr = new int[arr.Length];
        int k = 0;
        for (int v = 0; v <= maxVal; v++) {
            while (counts[v]-- > 0) outArr[k++] = v;
        }
        return outArr;
    }

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

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), а сравнения стали узким местом». Решение на нём обычно укладывается в O(n).

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

Слова в условии для всех паттернов собраны в одной таблице: шпаргалка по паттернам алгоритмов.

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

Паттерн «Сортировка без сравнений (подсчётом / поразрядная)» чаще всего путают с этими паттернами: Быстрая сортировка (merge / quick), Хеш-множество / словарь, Сортировка с пользовательским компаратором и Элементарные сортировки (выбором, пузырьком, вставками).

• Быстрая сортировка (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 самых частых элементов, Индекс Хирша, Максимальный разрыв, Относительная сортировка массива и Сортировка символов по частоте.

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

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

У паттерна «Сортировка без сравнений (подсчётом / поразрядная)» целевая сложность O(n).

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