Счетная сортировка - Counting sort

Счетная сортировка
Класс Алгоритм сортировки
Структура данных Множество
Наихудшая производительность , где k - диапазон неотрицательных значений ключа.
Сложность пространства в наихудшем случае

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

Подсчетная сортировка - это не сортировка сравнения ; он использует ключевые значения в качестве индексов в массиве, и нижняя граница Ω ( n log n ) для сортировки сравнения не применяется. Сортировка по корзине может использоваться вместо сортировки по счетчику и влечет за собой аналогичный временной анализ. Однако, по сравнению с сортировкой подсчетом, сортировка по корзине требует связанных списков , динамических массивов или большого количества предварительно выделенной памяти для хранения наборов элементов в каждой корзине, тогда как сортировка с подсчетом хранит одно число (количество элементов) для каждой корзины. .

Предположения на входе и выходе

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

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

Результатом является массив элементов, упорядоченных по их ключам. Из-за того, что она применяется к сортировке по основанию счисления, сортировка с подсчетом должна быть стабильной ; то есть, даже если два элемента имеют один и тот же ключ, их относительное положение в выходном массиве и их относительное положение во входном массиве должны совпадать.

Псевдокод

В псевдокоде алгоритм может быть выражен как: 

function CountingSort(input, k)
    
    count ← array of k + 1 zeros
    output ← array of same length as input
    
    for i = 0 to length(input) - 1 do
        j = key(input[i])
        count[j] += 1

    for i = 1 to k do
        count[i] += count[i - 1]

    for i = length(input) - 1 downto 0 do
        j = key(input[i])
        count[j] -= 1
        output[count[j]] = input[i]

    return output

Вот inputвходной массив для сортировки, keyвозвращает числовой ключ каждого элемента во входном массиве, countэто вспомогательный массив, используемый сначала для хранения количества элементов с каждым ключом, а затем (после второго цикла) для хранения позиций, в которых элементы с каждым ключом должны быть размещены, kявляется максимальным значением неотрицательных значений ключа и outputявляется отсортированным выходным массивом.

Таким образом, алгоритм перебирает элементы в первом цикле, вычисляя гистограмму количества раз, когда каждый ключ встречается в inputколлекции. После этого во втором цикле он выполняет вычисление суммы префиксаcount , чтобы определить для каждого ключа диапазон позиций, в котором должны быть размещены элементы, имеющие этот ключ; т.е. ключевые элементы должны быть помещены в исходное положение . Наконец, в третьем цикле он снова перебирает элементы , но в обратном порядке, перемещая каждый элемент в свою отсортированную позицию в массиве. count[]inputoutput

Здесь сохраняется относительный порядок элементов с одинаковыми ключами; т.е. это стабильный сорт .

Анализ сложности

Поскольку алгоритм использует только простые циклы for, без рекурсии или вызовов подпрограмм, его легко анализировать. Инициализация массива count и второй цикл for, который выполняет префиксную сумму для массива count, каждая повторяется не более k + 1 раз и, следовательно, занимает время O ( k ) . Два других цикла for и инициализация выходного массива занимают время O ( n ) . Следовательно, время для всего алгоритма - это сумма времени для этих шагов, O ( n + k ) .

Поскольку он использует массивы длины k + 1 и n , общее использование пространства алгоритмом также составляет O ( n + k ) . Для проблемных случаев, в которых максимальное значение ключа значительно меньше, чем количество элементов, сортировка с подсчетом может быть очень эффективной по пространству, поскольку единственное хранилище, которое она использует, кроме входных и выходных массивов, - это массив Count, который использует пространство O ( k ) .

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

Если каждый элемент для сортировки сам по себе является целым числом и также используется в качестве ключа, то второй и третий циклы сортировки с подсчетом могут быть объединены; во втором цикле вместо вычисления позиции, в которой элементы с ключом iдолжны быть помещены в вывод, просто добавьте Count[i]копии числа iк выводу.

Этот алгоритм также может использоваться для устранения повторяющихся ключей путем замены Countмассива битовым вектором, в котором хранится a oneдля ключа, присутствующего во входных данных, и a zeroдля ключа, которого нет. Если дополнительно элементы сами являются целочисленными ключами, и второй, и третий циклы могут быть полностью опущены, а битовый вектор сам будет служить выходом, представляя значения как смещения не- zeroвходов, добавленных к наименьшему значению диапазона. Таким образом, ключи сортируются, а дубликаты удаляются в этом варианте, просто помещаясь в битовый массив.

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

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

История

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

использованная литература

внешние ссылки