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

Введение

Алгоритм сортировки

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

Варианты алгоритмов

Если каждый элемент, подлежащий сортировке, сам является целым числом и используется в качестве ключа, то второй и третий циклы сортировки подсчётом можно объединить. Во втором цикле, вместо вычисления позиции, в которую следует поместить элементы с ключом i в выходной массив, просто добавьте Count[i] копий числа i к выходному массиву. Этот алгоритм также можно использовать для удаления повторяющихся ключей, заменив массив Count битовым вектором, который хранит единицу для ключа, присутствующего во входных данных, и ноль для ключа, отсутствующего во входных данных. Если элементы дополнительно являются самими целыми ключами, то и второй, и третий циклы можно опустить полностью, и битовый вектор сам будет служить выходными данными, представляя значения как смещения ненулевых элементов, добавленные к минимальному значению диапазона. Таким образом, в этом варианте ключи сортируются, а дубликаты удаляются, просто помещая их в битовый массив. Для данных, в которых максимальный размер ключа значительно меньше, чем количество элементов данных, сортировку подсчётом можно распараллелить, разделив входные данные на подмассивы примерно одинакового размера, обрабатывая каждый подмассив параллельно для создания отдельного массива подсчёта для каждого подмассива, а затем объединяя массивы подсчёта. При использовании в качестве части алгоритма параллельной поразрядной сортировки размер ключа (основание поразрядного представления) должен соответствовать размеру разделенных подмассивов. Простота алгоритма сортировки подсчётом и его использование легко распараллеливаемой операции префиксной суммы также делают его применимым в более мелкозернистых параллельных алгоритмах. Как описано, сортировка подсчётом не является алгоритмом "на месте"; даже не учитывая массив подсчёта, ей требуются отдельные входной и выходной массивы. Можно изменить алгоритм так, чтобы он помещал элементы в отсортированном порядке в тот же массив, который был ему дан на вход, используя только массив подсчёта в качестве вспомогательного хранилища; однако, модифицированная версия сортировки подсчётом не является стабильной.