Введение в счетный вид

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

Алгоритм был впервые описан Гарольдом Х. Сьюардом в 1954 году и остается основополагающей техникой в информатике. Его простота и эффективность делают его идеальным для таких задач, как сортировка возрастов студентов, оценок или любых целочисленных данных со скромным спредом. Используя вспомогательное хранилище, пропорциональное диапазону значений, Counting Sort избегает нижней границы сортировки сравнения O(n log n), достигая времени O(n + k), где k - диапазон входных значений.

Как работает счетчик

Основной механизм Counting Sort прост: он подсчитывает, сколько раз каждое значение появляется во входном массиве, а затем использует это количество для вычисления конечного положения каждого элемента. Процесс состоит из трех отдельных фаз:

  1. Рассчитывание: Создать счетный массив размера k (диапазон входных значений), инициализированный до нуля. Итерировать через входной массив и увеличивать счет для каждого значения.
  2. Вычислительные префиксы: Преобразуйте счетный массив в префиксный суммарный массив, где каждый элемент в индексе i удерживает кумулятивное количество элементов меньше или равно i. Этот шаг определяет исходные позиции для каждого отдельного значения в сортированном выходе.
  3. Элементы размещения: Пересекайте входной массив справа налево (для стабильности), используйте счетный массив, чтобы найти правильный индекс в выходном массиве, поместите элемент там и уменьшите счет.

Алгоритм возвращает новый сортированный массив, оставляя исходный неизмененным. Вариант под названием в месте Сортировки счёта существует, но редко используется, поскольку он ставит под угрозу стабильность или эффективность пространства.

Шаг за шагом Пример

Рассмотрим сортировку массива [4, 2, 2, 8, 3, 3, 1], где значения варьируются от 0 до 8.

  1. Счет: Счет массива размером 9 (0-8) → [0,1,2,2,1,0,0,0,1]. (Индекс 1 появляется один раз, индекс 2 дважды, индекс 3 дважды, индекс 4 один раз, индекс 8 один раз).
  2. Результаты префикса: Преобразование в кумулятивное → [0,1,3,5,6,6,6,6,7]. Теперь каждое значение сообщает нам исходное положение для этого числа в сортированном выходе.
  3. Выход: Поперечный исходный массив от конца: первый элемент читается как 1 → положение = счёт[1] — 1 = 0 → выход[0] = 1, счёт декрементов[1] — 0. Далее 3 → положение = счёт[3] — 1 = 4 → вывод[4] = 3, счёт[3] = 4. Продолжайте до тех пор, пока не будут размещены все элементы. Окончательный вывод: [1,2,2,3,3,4,8].

Этот пример показывает, как Counting Sort полностью избегает сравнений, полагаясь исключительно на арифметические операции.

Вычислительная сложность

Сложность времени

  • Наилучший, средний и худший случай: O(n + k), где n — число элементов и k — диапазон входных значений.Когда k мало относительно n, алгоритм работает в линейном времени.
  • Сравнение сортировок сравнения: У Quicksort и Mergesort средняя сложность O(n log n) Для n = 106 и k = 1000, Counting Sort (≈ 1 001 000 операций) примерно в 13 раз быстрее, чем типичный O(n log n) сорт.

Космическая сложность

  • Первичное: O(k) для массива счётчиков, плюс O(n) для выходного массива. Эта накладная память может быть непомерно большой, если k (например, сортировка 32-битных целых чисел, где k = 232).
  • Стабильный вариант: Требует вспомогательного выходного массива размером n; на месте варианты жертвуют стабильностью или используют сложные манипуляции с индексами.

Когда использовать счетный сорт

Сортировка наиболее эффективна при следующих условиях:

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

Отличные варианты использования включают сортировку классов (0-100), возрастов (0-120), категорий продуктов (до нескольких сотен SKU) или в качестве подпрограммы в Radix Sort .

Ограничения и соображения

Несмотря на свою скорость, Counting Sort имеет недостатки, которые ограничивают его применимость:

  • Целое число: Он не может непосредственно сортировать числа или строки с плавающей точкой, если они не преобразованы в смежный набор целых чисел.
  • Большой диапазон: Если k затмевает n — например, сортируя 100 чисел со значениями от 1 до 107 — массив счётчиков потребляет огромную память при сортировке лишь нескольких элементов.
  • Неадаптивный: Сортировка счёта всегда требует сканирования всего входного и построения счётного массива, даже если данные уже отсортированы или почти отсортированы.
  • Отрицательные значения: Стандартная счетная сортировка предполагает неотрицательные целые числа.Для обработки отрицательных значений можно сместить значения, вычитая минимум (делая диапазон от 0 до максимума — мин).

Эти ограничения означают, что Counting Sort является специализированным инструментом, а не универсальной заменой алгоритмов общего назначения.

Сравнение с соответствующими алгоритмами сортировки

Сортировка по сравнению с Radix Sort

Radix Sort расширяет идею путем сортировки цифр от наименее значимых до наиболее значимых, используя стабильный сорт (часто Counting Sort) на каждой цифре.В то время как Counting Sort работает на одном проходе по всему диапазону k, Radix Sort выполняет несколько проходов по меньшему диапазону цифр (например, основание 256), уменьшая использование памяти для большого k. Например, сортировка 32-битных целых чисел с Counting Sort потребует массива 232 записей, тогда как Radix Sort с 8-битными цифрами требует 256 записей на проход и только четыре прохода.

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

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

Реализация стабильного способа подсчета

Стабильность важна при сортировке по одному ключу при сохранении относительного порядка равных элементов из другого ключа. Стандартный алгоритм Counting Sort по своей сути стабилен, когда петля размещения вывода пересекает вход справа налево. Вот текстовый контур стабильного варианта:

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

Поскольку мы обрабатываем элементы с конца, последнее появление данного значения переходит в максимально возможный индекс, сохраняя относительный порядок. Эта стабильная версия необходима для правильной работы Radix Sort на каждой цифре.

Практические применения

  • Системы оценки образования: Сортировка сотен баллов экзамена (диапазон 0-100) во время O(n) .
  • Биоинформатика: Сортировка целых чисел считывает числа или частоты k-мера ДНК, когда размер алфавита мал (A, C, G, T).
  • Поддерживание индекса базы данных: Сортировка уникальных целых идентификаторов в диапазоне, достаточно малом, чтобы вписаться в память.
  • Обработка изображений: Сортировка гистограммных урн или интенсивностей цвета (0–255) при построении таблиц поиска.
  • Сортировка по вторичному ключу: Используется внутри Radix Sort, который является рабочей лошадкой для эффективной сортировки во многих библиотеках и языках (например, в .NET Runtime используется адаптивное сочетание алгоритмов, включая Counting Sort для небольших диапазонов).

Для получения дополнительной информации о теории и вариантах, обратитесь к авторитетным ссылкам, таким как Википедия: Сортировка подсчета и GeeksforGeeks: Сортировка подсчета . Практические сравнения с другими алгоритмами можно найти в

Оптимизация счётного сорта для больших диапазонов

Когда k велико, но n также велико, чистый счет становится интенсивным для памяти.

  • Сжатая разреженность: Используйте хеш-карту вместо смежного массива, когда диапазон используемых значений большой, но количество различных значений мало. Это торгует индексированием в постоянное время для хеширования накладных расходов, но снижает потребление памяти.
  • Гибридные подходы: Объединить Сортировку Счета с другими алгоритмами. Например, если диапазон превышает 106, используйте Сортировку Радикса с основанием, которое сохраняет диапазоны цифр небольшими.
  • На месте варианты: Некоторые оптимизации уменьшают дополнительное пространство до O(k) без выходного массива, но они обычно жертвуют стабильностью или требуют циклов для определения позиций.

Заключение

Сортировка по счету выделяется как удивительно эффективный алгоритм сортировки целых чисел, когда диапазон значений мал по отношению к числу элементов. Его сложность во времени O(n + k) и линейная производительность делают его незаменимым в таких сценариях, как сортировка по классам, подпрограммы Radix Sort и приложения с ограниченными целочисленными ключами. Однако зависимость алгоритма от ввода целых чисел и накладных расходов на память для больших диапазонов напоминает нам, что ни один сорт не является оптимальным для всех ситуаций. Понимая, когда сортировка по счету превосходит - и когда она терпит неудачу - разработчики могут создавать более быстрые, более предсказуемые системы. Для дальнейшего чтения на сортировке на основе несравнений см. Туториальная точка: Сортировка по счету и Сортировка: Сортировка лекций .