Сортировка подсчётом и устойчивость

Все сортировки из предыдущих статей сравнивают элементы между собой. Быстрее чем $O(n \log n)$ такая сортировка в общем случае работать не может — это доказано. Но если про значения известно что-то ещё, доказательство к делу не относится.

Идея

Пусть все элементы — целые числа от $0$ до $C$. Заведём массив счётчиков длины $C + 1$ и посчитаем, сколько раз встречается каждое значение. Потом пройдём по счётчикам по возрастанию и выпишем каждое значение столько раз, сколько оно встретилось.

vector<int> cnt(C + 1, 0);
for (int value : a) cnt[value]++;

int pos = 0;
for (int value = 0; value <= C; value++)
    for (int t = 0; t < cnt[value]; t++)
        a[pos++] = value;

На массиве 1 2 2 1 0 счётчики получатся 1 2 2, и обратно запишутся сначала один ноль, потом две единицы, потом две двойки.

Почему это n + C, а не n · C

Вложенный цикл смущает: кажется, что для каждого из $C$ значений мы что-то делаем много раз. Но внутренний цикл выполняется ровно cnt[value] раз, а сумма всех cnt[value] — это $n$, число элементов. Каждый элемент записывается один раз.

Внешний цикл делает $C$ шагов, подсчёт — $n$. Итого $O(n + C)$.

Отрицательные числа и сдвиг

Если значения бывают от $-10^5$ до $10^5$, обращение cnt[value] уедет в отрицательный индекс. Лечится сдвигом: вычитаем из каждого значения минимум.

Тот же приём спасает и в другом случае. Если числа лежат от $10^9 - 100$ до $10^9$, диапазон огромен, а разброс — всего сто. После вычитания минимума значения оказываются от $0$ до $100$, и массив счётчиков нужен крошечный.

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

Когда это выгодно

Сравнивать надо $n + C$ с $n \log n$.

Если $n = 10^7$ и значения тоже до $10^7$ — подсчёт заметно быстрее, обычная сортировка на таком размере скорее всего не пройдёт по времени. Если $n = 10^5$, а значения до $10^9$ — про подсчёт можно забыть, $n \log n$ вне конкуренции.

Правило простое: подсчёт выигрывает, когда элементов много, а различных значений мало.

Почему не словарь

Соблазнительно заменить массив счётчиков на map и не думать про диапазон. Так делать не стоит: обращение к map стоит логарифм, и линейный алгоритм превращается в $O(n \log n)$ с очень неприятной константой. Проход по массиву из $10^6$ элементов со вставкой в map или set — типичная причина превышения лимита времени.

Хеш-таблица обращение ускоряет, но не спасает: по ней нельзя пройтись по возрастанию ключей, а именно это подсчёту и нужно.

Устойчивость

Представьте очередь в поликлинику. Хочется пустить вперёд тех, кто старше, — отсортировать по возрасту. Но если двум бабушкам по семьдесят, справедливо, чтобы вперёд прошла та, которая пришла раньше.

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

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

Подсчёт устойчивым не является

В том виде, как выше, — нет: мы вообще не смотрим, кто где стоял, а просто выписываем значения по счётчику.

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

vector<vector<string>> names(C + 1);
for (auto& [age, name] : people) names[age].push_back(name);

int pos = 0;
for (int age = 0; age <= C; age++)
    for (auto& name : names[age])
        people[pos++] = {age, name};

Внутри каждого возраста имена лежат в том порядке, в котором встретились, — а значит и выписаны будут в нём же. Асимптотика та же $O(n + C)$, но памяти теперь нужно $O(n + C)$, а не $O(C)$.

Что делать, когда диапазон всё-таки велик

Подсчёт упирается в размер диапазона, и при значениях до $10^9$ массив счётчиков завести не выйдет. Но выход есть: число можно разобрать на разряды и отсортировать по каждому отдельно, применяя подсчёт много раз. Так получается поразрядная сортировка — ей посвящена отдельная статья, и держится она как раз на устойчивости.

Универсальный способ

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

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