Информатика · объяснение и практика

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

Сортировка подсчётом: частоты целых ключей, сдвиг отрицательного диапазона и отличие числа значений от ширины диапазона.

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Методы алгоритмов: углубление · Учебная карта

В маршруте Сортировки и сравнение строк · 10 тем

Главная мысль

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

Для какого набора подходит таблица частот

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

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

Сдвигаем отрицательные ключи

Для целых от минимума m до максимума M индекс можно вычислять как x−m. Тогда самый маленький ключ попадает в ячейку ноль, а самый большой — в последнюю. Ширина таблицы равна M−m+1. Само значение числа при этом не меняется: сдвиг относится только к адресу его счётчика.

Возьмём набор −3,−1,−3,0. Здесь минимум−3, максимум 0, поэтому нужны четыре ячейки. В них последовательно записаны частоты 2,0,1,1 для ключей−3,−2,−1,0. Чтобы получить отсортированные голые числа, можно выписать каждый ключ столько раз, сколько показывает его частота.

Пример

Вход: [−3,−1,−3,0]. Частоты для ключей [−3,−2,−1,0]: [2,0,1,1]. Итог: [−3,−3,−1,0].

Нулевая частота для−2 не означает пропущенную ячейку. Именно полный диапазон позволяет напрямую получить индекс как x+3.

Если вместе с ключом надо сохранить запись

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

В стандартном стабильном варианте с накопленными концами блоков вход обходят справа налево. Для каждого ключа сначала уменьшают его границу, затем помещают запись в освободившуюся позицию. Память выходного массива тоже учитывается. Метод полезен при подходящем диапазоне, но не становится универсально лучшим только потому, что не сравнивает ключи попарно.

От чтения к действию

А теперь — вы

Есть только значения 1 и 1000001. Сколько ячеек нужно прямой таблице для всех целых от минимума до максимума?

Частые вопросы

Можно сортировать отрицательные целые?

Да. Адрес счётчика получают сдвигом x−min; число возможных адресов равно max−min+1.

Частоты достаточно для сортировки записей с именами?

Нет. Частоты сами по себе не сохраняют дополнительные поля исходных записей; нужен перенос записей в вычисленные позиции.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться