Подсчет сортировки
| Сорт | Алгоритм сортировки |
|---|---|
| Структура данных | Множество |
| Худшая производительность | , где k — диапазон неотрицательных значений ключа. |
| Наихудшая пространственная сложность |
В информатике положительные счетная сортировка — это алгоритм сортировки ; набора объектов по ключам, которые представляют собой небольшие числа целые то есть это алгоритм сортировки целых чисел . Он работает путем подсчета количества объектов, которые обладают различными значениями ключей, и применения суммы префиксов к этим счетчикам для определения позиций каждого значения ключа в выходной последовательности. Время его работы линейно зависит от количества элементов и разницы между максимальным значением ключа и минимальным значением ключа, поэтому оно подходит для прямого использования только в ситуациях, когда изменение ключей не значительно превышает количество элементов. Он часто используется как подпрограмма в поразрядной сортировке , другом алгоритме сортировки, который может более эффективно обрабатывать большие ключи. [1] [2] [3]
Сортировка подсчетом не является сортировкой сравнения ; он использует ключевые значения в качестве индексов в массиве, и Ω ( n log n ) нижняя граница для сортировки сравнения не применяется. [1] Сортировка по сегментам может использоваться вместо сортировки по подсчету и влечет за собой аналогичный временной анализ. Однако по сравнению с сортировкой по подсчету, сортировка по сегментам требует связанных списков , динамических массивов или большого объема заранее выделенной памяти для хранения наборов элементов в каждом сегменте, тогда как сортировка по подсчету сохраняет одно число (количество элементов) для каждого сегмента. . [4]
Предположения о входных и выходных данных
[ редактировать ]В самом общем случае входные данные для сортировки по подсчету состоят из набора из n элементов, каждый из которых имеет неотрицательный целочисленный ключ, максимальное значение которого не превышает k . [3] В некоторых описаниях сортировки по подсчету предполагается, что входные данные, подлежащие сортировке, представляют собой просто последовательность целых чисел. [1] но это упрощение не подходит для многих приложений счетного типа. Например, при использовании в качестве подпрограммы поразрядной сортировки ключами для каждого вызова подсчетной сортировки являются отдельные цифры более крупных ключей элементов; было бы недостаточно вернуть только отсортированный список ключевых цифр, отделенных от элементов.
В таких приложениях, как поразрядная сортировка, граница максимального значения ключа k будет известна заранее и может считаться частью входных данных алгоритма. Однако, если значение k еще не известно, его можно вычислить в качестве первого шага с помощью дополнительного цикла по данным для определения максимального значения ключа.
Выходные данные представляют собой массив элементов, упорядоченных по их ключам. Поскольку счетная сортировка применяется к поразрядной сортировке, она должна быть стабильной сортировкой ; то есть, если два элемента имеют один и тот же ключ, их относительный порядок в выходном массиве и их относительный порядок во входном массиве должны совпадать. [1] [2]
Псевдокод
[ редактировать ]В псевдокоде алгоритм можно выразить так:
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] = count[j] + 1
for i = 1 to k do
count[i] = count[i] + count[i - 1]
for i = length(input) - 1 down to 0 do
j = key(input[i])
count[j] = count[j] - 1
output[count[j]] = input[i]
return output
Здесь input это входной массив, который нужно отсортировать, key возвращает числовой ключ каждого элемента входного массива, count — это вспомогательный массив, используемый сначала для хранения количества элементов с каждым ключом, а затем (после второго цикла) для хранения позиций, в которых должны быть размещены элементы с каждым ключом,
k — максимальное значение неотрицательных значений ключа и output это отсортированный выходной массив.
Короче говоря, алгоритм перебирает элементы в первом цикле, вычисляя гистограмму количества раз, когда каждый ключ встречается в пределах input коллекция. После этого во втором цикле он выполняет вычисление суммы префикса для count для определения для каждого ключа диапазона позиций, в котором должны быть размещены элементы, имеющие этот ключ; т.е. ключевые элементы следует размещать, начиная с позиции count[]. Наконец, в третьем цикле он перебирает элементы input еще раз, но в обратном порядке, перемещая каждый элемент в отсортированное положение в output множество. [1] [2] [3]
Здесь сохраняется относительный порядок элементов с одинаковыми ключами; т. е. это стабильный сорт .
Анализ сложности
[ редактировать ]Поскольку алгоритм использует только простые for циклы, без рекурсии или вызовов подпрограмм, их легко анализировать. Инициализация массива счетчиков и второй цикл for, который выполняет суммирование префикса в массиве счетчиков, каждая итерация выполняется не более k + 1 раз и, следовательно, занимает время O ( k ) . Два других цикла for и инициализация выходного массива занимают время O ( n ) . Следовательно, время всего алгоритма представляет собой сумму времени этих шагов O ( n + k ) . [1] [2]
Поскольку он использует массивы длины k +1 и n , общее использование пространства алгоритмом также равно O ( n + k ) . [1] В тех случаях, когда максимальное значение ключа значительно меньше количества элементов, сортировка по подсчету может быть очень экономичной, поскольку единственным хранилищем, которое она использует, кроме входных и выходных массивов, является массив Count, который использует пространство O ( k ) . [5]
Варианты алгоритмов
[ редактировать ]Если каждый сортируемый элемент сам по себе является целым числом и также используется в качестве ключа, то второй и третий циклы счетной сортировки можно объединить; во втором цикле вместо вычисления позиции, в которой находятся элементы с ключом i должен быть помещен в вывод, просто добавьте Count[i] копии номера i к выходу.
Этот алгоритм также можно использовать для устранения дубликатов ключей путем замены Count массив с битовым вектором , в котором хранится one для ключа, который присутствует во входных данных, и zero для ключа, которого нет. Если, кроме того, элементы сами являются целочисленными ключами, то второй и третий циклы можно полностью опустить, и сам битовый вектор будет служить выходом, представляя значения как смещения не- zero записи, добавленные к наименьшему значению диапазона. Таким образом, в этом варианте ключи сортируются, а дубликаты удаляются просто путем помещения в битовый массив.
Для данных, в которых максимальный размер ключа значительно меньше количества элементов данных, сортировку подсчетом можно распараллелить путем разделения входных данных на подмассивы примерно одинакового размера, параллельной обработки каждого подмассива для создания отдельного массива подсчетов для каждого подмассива и затем объединение массивов счетчиков. При использовании в качестве части параллельного алгоритма поразрядной сортировки размер ключа (база представления поразрядной системы) должен выбираться так, чтобы он соответствовал размеру разделенных подмассивов. [6] Простота алгоритма сортировки подсчетом и использование в нем легко распараллеливаемого примитива суммы префиксов также делают его пригодным для использования в более детальных параллельных алгоритмах. [7]
Как описано, сортировка по подсчету не является алгоритмом на месте ; даже несмотря на массив счетчиков, ему нужны отдельные массивы ввода и вывода. Можно изменить алгоритм так, чтобы он размещал элементы в отсортированном порядке в том же массиве, который был передан ему в качестве входных данных, используя только массив счетчиков в качестве вспомогательного хранилища; однако модифицированная версия сортировки по месту не является стабильной. [3]
История
[ редактировать ]Хотя поразрядная сортировка возникла гораздо раньше, Сортировка подсчетом и ее применение к поразрядной сортировке были изобретены Гарольдом Х. Сьюардом в 1954 году. [1] [4] [8]
Ссылки
[ редактировать ]- ^ Jump up to: Перейти обратно: а б с д и ж г час Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001), «Сортировка подсчетом 8.2», Введение в алгоритмы (2-е изд.), MIT Press и McGraw-Hill , стр. 168–170, ISBN 0-262-03293-7 . См. также исторические заметки на стр. 181.
- ^ Jump up to: Перейти обратно: а б с д Эдмондс, Джефф (2008), «Сортировка подсчетом 5.2 (стабильная сортировка)», Как думать об алгоритмах , Cambridge University Press, стр. 72–75, ISBN 978-0-521-84931-9 .
- ^ Jump up to: Перейти обратно: а б с д Седжвик, Роберт (2003), «6.10 Индексированный по ключам подсчет», Алгоритмы в Java, Части 1–4: Основы, структуры данных, сортировка и поиск (3-е изд.), Аддисон-Уэсли, стр. 312–314 .
- ^ Jump up to: Перейти обратно: а б Кнут, DE (1998), Искусство компьютерного программирования , Том 3: Сортировка и поиск (2-е изд.), Аддисон-Уэсли, ISBN 0-201-89685-0 . Раздел 5.2, Сортировка по подсчету, стр. 75–80, и исторические примечания, стр. 170.
- ^ Беррис, Дэвид С.; Шембер, Курт (1980), «Сортировка последовательных файлов с ограниченным дополнительным хранилищем», Труды 18-й ежегодной Юго-восточной региональной конференции , Нью-Йорк, Нью-Йорк, США: ACM, стр. 23–31, doi : 10.1145/503838.503855 , ISBN 0897910141 , S2CID 5670614 .
- ^ Зага, Марко; Блеллок, Гай Э. (1991), «Поразрядная сортировка для векторных мультипроцессоров», Proceedings of Supercomputing '91, 18–22 ноября 1991 г., Альбукерке, Нью-Мексико, США , Компьютерное общество IEEE / ACM, стр. 712–721, doi : 10.1145/125826.126164 , ISBN 0897914597 .
- ^ Рейф, Джон Х. (1985), «Оптимальный параллельный алгоритм сортировки целых чисел», Proc. 26-й ежегодный симпозиум по основам информатики (FOCS 1985) , стр. 496–504, doi : 10.1109/SFCS.1985.9 , ISBN 0-8186-0644-4 , S2CID 5694693 .
- ^ Сьюард, Х.Х. (1954), «2.4.6 Внутренняя сортировка посредством плавающей цифровой сортировки», Сортировка информации при применении электронных цифровых компьютеров в бизнес-операциях (PDF) , магистерская диссертация, Отчет R-232, Массачусетский технологический институт , Цифровой компьютер Лаборатория, стр. 25–28 .
Внешние ссылки
[ редактировать ]
- Подсчет сортировки HTML5 визуализация
- Демонстрационный апплет из Кардиффского университета. Архивировано 2 июня 2013 г. в Wayback Machine.
- Кагель, Арт С. (2 июня 2006 г.), «Сортировка подсчетом», в Блэке, Поле Э. (ред.), Словарь алгоритмов и структур данных , Национальный институт стандартов и технологий США , получено 21 апреля 2011 г.