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

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

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

Поскольку при подсчетной сортировке значения ключей используются как индексы в массиве, это не сортировка сравнения, а Ω (п журнал п) нижняя граница для сравнения сортировка к нему не применяется.[1] Ковшовая сортировка может использоваться для многих из тех же задач, что и сортировка подсчетом, с аналогичным временным анализом; однако, по сравнению с сортировкой подсчетом, сортировка по ведру требует связанные списки, динамические массивы или большой объем предварительно выделенной памяти для хранения наборов элементов в каждой корзине, тогда как сортировка с подсчетом вместо этого хранит одно число (количество элементов) для каждой корзины.[4]

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

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

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

На выходе получается массив элементов в порядке их ключей. Из-за приложения к сортировке по основанию счисления важно, чтобы сортировка подсчета была стабильная сортировка: если два элемента имеют один и тот же ключ, они должны иметь такое же относительное положение на выходе, что и на входе.[1][2]

Алгоритм

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

считать = массив из k + 1 нулейдля Икс в ввод делать    счетчик [ключ (Икс)] += 1Всего = 0для я в 0, 1, ... к делать    count [i], Всего = Всего, count [я] + Всеговывод = массив той же длины, что и вводдля Икс в ввод делать    вывод[считать[ключ (Икс)]] = Икс    считать[ключ (Икс)] += 1 вернуть вывод

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

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

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

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

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

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

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

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

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

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

История

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

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

  1. ^ а б c d е ж г час Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (2001), "8.2 Сортировка подсчета", Введение в алгоритмы (2-е изд.), MIT Press и Макгроу-Хилл, стр. 168–170, ISBN  0-262-03293-7. См. Также исторические заметки на странице 181.
  2. ^ а б c d Эдмондс, Джефф (2008), «5.2 Подсчет сортировки (стабильная сортировка)», Как думать об алгоритмах, Cambridge University Press, стр. 72–75, ISBN  978-0-521-84931-9.
  3. ^ а б c d Седжвик, Роберт (2003), «6.10 Подсчет с индексированием по ключу», Алгоритмы на Java, части 1-4: основы, структуры данных, сортировка и поиск (3-е изд.), Addison-Wesley, pp. 312–314.
  4. ^ а б Кнут, Д. Э. (1998), Искусство программирования, Том 3: Сортировка и поиск (2-е изд.), Эддисон-Уэсли, ISBN  0-201-89685-0. Раздел 5.2, Сортировка по счету, стр. 75–80, и исторические заметки, стр. 170.
  5. ^ Беррис, Дэвид С .; Шембер, Курт (1980), "Сортировка последовательных файлов с ограниченным объемом вспомогательной памяти", Материалы 18-й ежегодной Юго-Восточной региональной конференции, Нью-Йорк, Нью-Йорк, США: ACM, стр. 23–31, Дои:10.1145/503838.503855, ISBN  0897910141.
  6. ^ Загха, Марко; Блеллох, Гай Э. (1991), "Радиксная сортировка для векторных мультипроцессоров", Proceedings of Supercomputing '91, 18-22 ноября 1991 г., Альбукерке, Нью-Мексико, США, IEEE Computer Society / ACM, стр. 712–721, Дои:10.1145/125826.126164, ISBN  0897914597.
  7. ^ Рейф, Джон Х. (1985), «Оптимальный параллельный алгоритм для целочисленной сортировки», Proc. 26-й ежегодный симпозиум по основам компьютерных наук (FOCS 1985), стр. 496–504, Дои:10.1109 / SFCS.1985.9, ISBN  0-8186-0644-4.
  8. ^ Сьюард, Х. Х. (1954), «2.4.6 Внутренняя сортировка с помощью плавающей цифровой сортировки», Сортировка информации в применении электронных цифровых компьютеров к бизнес-операциям (PDF), Магистерская работа, Отчет Р-232, Массачусетский Институт Технологий, Лаборатория цифровых компьютеров, стр. 25–28..

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