Сортировка подсчётом: считать вместо того, чтобы сравнивать

Если ты умеешь сортировать подсчётом за Θ(n+k), понимаешь, почему это обходит границу n·log n, и знаешь ограничение (целые в небольшом диапазоне), листай до «Теперь сам».

Как думаешь, как отсортировать, вообще не сравнивая элементы

Прошлый урок доказал: сравнениями быстрее n·log n нельзя. Значит, чтобы сортировать за линию, надо перестать спрашивать «какой из двух больше». Но как тогда узнать порядок? Через само ЗНАЧЕНИЕ. Если элементы - целые числа от 0 до, скажем, 11, то значение можно использовать как АДРЕС: число 7 «знает» своё место - оно идёт после всех 6 и перед всеми 8. Не надо сравнивать 7 с соседями - надо просто посчитать, сколько каких чисел, и выписать их по порядку значений. Это и есть сортировка подсчётом.

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

Ты разбираешь ящик с монетами номиналом 1, 2, 5, 10 рублей. Ты не сравниваешь монеты попарно - ты раскладываешь их по КУЧКАМ: рубли к рублям, двушки к двушкам. Потом пересчитываешь кучки и говоришь: «15 монет по рублю, 8 по два, ...». Чтобы выложить их по возрастанию, ты просто берёшь кучки по порядку номинала. Ни одного сравнения «эта монета больше той» - только сортировка по заранее известным «ячейкам» номиналов и подсчёт.

Механизм: посчитать и выписать

Пусть все элементы - целые в диапазоне [0, k).

1. Завести счётчики. Массив count размера k, заполненный нулями: count[v] будет хранить, сколько раз встретилось значение v.
2. Посчитать. Один проход по a: для каждого x увеличиваем count[x] на 1. Это Θ(n) - по одному действию на элемент, БЕЗ сравнений.
3. Выписать. Идём по значениям v от 0 до k−1 и добавляем v в результат ровно count[v] раз. Это Θ(n + k): k шагов по счётчикам плюс n записей значений.

Правило

Сортировка подсчётом упорядочивает целые из диапазона [0, k) за Θ(n + k), не делая ни одного сравнения: посчитать, сколько раз встречается каждое значение (массив count размера k), затем выписать значения по порядку нужное число раз. Она обходит границу n·log n, потому что адресуется по значению, а не сравнивает. Условие применимости - ключи целые и диапазон k не слишком широк (иначе count раздувается).

Разбор: почему это не противоречит нижней границе

Нижняя граница n·log n из прошлого урока - про сортировки СРАВНЕНИЯМИ, и её доказательство (дерево решений с двоичными развилками) опирается на то, что единственная операция - сравнение двух элементов. Сортировка подсчётом не делает НИ ОДНОГО сравнения: она использует значение элемента как индекс в массиве счётчиков. Её шаг «count[x] += 1» - это не развилка «больше/меньше», а прямая адресация. Поэтому дерево решений к ней неприменимо, и граница на неё не распространяется. Никакого противоречия: n·log n - стена для одного класса алгоритмов, а подсчёт играет по другим правилам и потому проходит сквозь неё.

Разбор: цена свободы - ограничение на данные

За линейное время подсчёт берёт двумя условиями. Первое: ключи должны быть ЦЕЛЫМИ (или сводимыми к целым индексам) - по дробному или произвольному объекту в массив не заиндексируешься. Второе: диапазон k не должен быть слишком большим. Стоимость Θ(n + k) хороша, пока k сравнимо с n (тогда это Θ(n)). Но если сортировать 1000 чисел, где значения - до миллиарда (k = 10⁹), массив счётчиков займёт миллиард ячеек: Θ(n + k) = Θ(10⁹) - катастрофа и по времени, и по памяти. Вывод: подсчёт незаменим для «плотных» данных (много элементов, мало разных значений - оценки, возрасты, буквы, байты), но бесполезен для широкого разреженного диапазона. Для больших ключей есть обходной приём - поразрядная сортировка (следующий урок), которая применяет подсчёт по ЦИФРАМ.

Разбор: устойчивость подсчёта

Сортировку подсчётом можно сделать УСТОЙЧИВОЙ - и это важно для поразрядной сортировки, которая на ней стоит. В простом варианте (выписать v по count[v] раз) устойчивость не видна, потому что мы сортируем голые числа - равные неразличимы. Но если с каждым ключом связан «груз» (запись, у которой ключ - лишь одно поле), то устойчивый вариант делают через ПРЕФИКСНЫЕ СУММЫ счётчиков: count[v] превращают в «сколько элементов со значением ≤ v», это даёт каждому значению диапазон позиций в результате, и элементы раскладывают, идя по входу и сохраняя их взаимный порядок. Тогда равные ключи остаются в исходном порядке - устойчивость, на которой держится поразрядная сортировка.

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

Первая ошибка - применить подсчёт к данным с ОГРОМНЫМ или неизвестным диапазоном значений: массив счётчиков размера k съест память и время, Θ(n + k) превратится в Θ(k). Подсчёт хорош только при малом k. Вторая - забыть, что подсчёт работает лишь с целыми (или ключами, сводимыми к целочисленному индексу): к дробным, строкам произвольной длины или объектам напрямую он неприменим. Третья - при отрицательных значениях индексироваться «в минус»: их надо сдвинуть (вычесть минимум), иначе count[x] вылетит за границы массива.

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

Сортировка подсчётом - рабочий инструмент там, где значений много, а РАЗНЫХ значений мало: отсортировать миллион оценок от 1 до 5, возрастов от 0 до 120, байтов от 0 до 255, символов алфавита. Во всех этих случаях k крохотное, и подсчёт даёт честную линию Θ(n) - быстрее любой сортировки сравнениями. Она же - фундамент поразрядной сортировки, которой сортируют большие целые и строки за линейное время. И это отличный практический урок: прежде чем тянуться к универсальной n·log n-сортировке, спроси - а какие у меня ключи? Если целые в узком диапазоне, подсчёт обгонит всё.

Теперь сам

Отсортируй подсчётом массив [2, 0, 2, 1, 0] по шагам: что окажется в счётчиках и как из них соберётся ответ? Сколько сравнений элементов друг с другом ты сделал?