'''Сортировка подсчётом''' {{---}} алгоритм сортировки целых чисел в диапазоне от <tex>0</tex> до некоторой константы <tex>k</tex> или сложных объектов, работающий за линейное время.
== Сортировка целочисленных значений целых чисел ===== Простой алгоритм ===<!-- Сделать нормальное описание -->
Это простейший вариант алгоритма. Создать вспомогательный массив <tex>C[0..k - 1]</tex>, состоящий из нулей, затем последовательно прочитать элементы входного массива <tex>A</tex> и для каждого <tex>A[i]</tex> увеличить <tex>C[A[i]]</tex> на единицу. Теперь достаточно пройти по массиву <tex>C</tex> и для каждого <tex>number \in \{0, ..., k - 1\}</tex> в массив <tex>A</tex> последовательно записать число <tex>number\</tex> <tex> C[number]</tex> раз.
<code>
SimpleCountingSort
for number = 0 to k - 1
C[number] = 0;
for i = 0 to length[A] - 1
C[A[i]] = C[A[i]] + 1;
pos = 0;
for number = 0 to k - 1
A[pos] = number;
pos = pos + 1;
</code>
=== Устойчивый алгоритм ===
==== Идея ====
Основная идея состоит в том, чтобы для каждого элемента входного массива подсчитать количество элементов, меньших данного. Эта информация будет указывать на позиции элементов в отсортированном массиве. Например, если для элемента <tex>x</tex> количество таких элементов будет <tex>42</tex>, то <tex>x</tex> будет занимать <tex>43</tex>-ю позицию в отсортированном массиве. Если элементы могут иметь одинаковые значения, то необходимо модифицировать алгоритм, так как нельзя разместить все такие элементы в одну позицию.
==== Реализация ====
В этом варианте помимо входного массива <tex>A</tex> потребуется два вспомогательных массива — <tex>C[0..k - 1]</tex> для счётчика и <tex>B[0..n - 1]</tex> для отсортированного массива. Сначала следует заполнить массив <tex>C</tex> нулями, и, пройдя по массиву <tex>A</tex>, записать количество чисел равных <tex>A[i]</tex> в массив <tex>C</tex> (строки 1 - 4). Далее подсчитывается число элементов меньше или равных текущему (строки 5 - 6). На последнем шаге алгоритма читается входной массив с конца, а в массив <tex>B</tex> записываются элементы на те позиции, где они должны стоять; эта информация хранится в массиве <tex>C</tex> (строки 7 - 9). Алгоритм устойчив. Устойчивость может потребоваться при [[Сортировка_подсчетом_сложных_объектов|сортировке сложных структур данных]].
<code>
StableCountingSort
for number = 0 to k - 1
C[number] = 0;
for i = 0 to length[A] - 1
C[A[i]] = C[A[i]] + 1;
for number = 1 to k - 1
C[j] = C[j] + C[j - 1];
for i = length[A] - 1 to 0
B[C[A[i]]] = A[i];
C[A[i]] = C[A[i]] - 1;
</code>
=== Обобщение на произвольный целочисленный диапазон ===
Если диапазон значений (минимимум и максимум) заранее не известен, можно найти их с помощью линейного поиска, что не повлияет на асимптотику алгоритма. При работе с массивом <tex>C</tex> из <tex>A[i]</tex> необходимо вычитать минимум, а при обратной записи прибавлять.
=== Анализ ===
В первом алгоритме первые два цикла работают за <tex>\Theta(k)</tex> и <tex>\Theta(n)</tex>, соответственно; двойной цикл за <tex>\Theta(n + k)</tex>. Во втором алгоритме циклы занимают <tex>\Theta(k)</tex>, <tex>\Theta(n)</tex>, <tex>\Theta(k)</tex> и <tex>\Theta(n)</tex>, соответственно. Итого оба алгоритма имеют линейную временную трудоёмкость <tex>\Theta(n + k)</tex>. Используемая память в первом алгоритме равна <tex>\Theta(k)</tex>, а во втором <tex>\Theta(n + k)</tex>.
Использование сортировки подсчётом целесообразно, когда диапазон возможных значений входных данных достаточно мал по сравнению с количеством элементов в сортируемом множестве, например, если <tex>n = 1000000</tex> и все элементы натуральные числа меньшие <tex>1000</tex>, то время работы алгоритма равно <tex>\Theta(n)</tex>. Эффективность алгоритма падает, когда необходимо сортировать различные элементы, попавшие в одну ячейку.
== Сортировка сложных объектов ==
=== Постановка задачи ===Сортировка целых чисел за линейное время это хорошо, но недостаточно. Иногда бывает очень желательно применить быстрый алгоритм [[#Сортировка подсчетомцелых чисел|сортировки подсчетом]] для упорядочивания набора каких-либо "сложных" данных. Под "сложными объектами" здесь подразумеваются структуры, содержащие в себе несколько полей. Одно из них мы выделим и назовем ключом, сортировка будет идти именно по нему (предполагается, что значения, принимаемые ключом {{---}} целые числа в диапазоне от <tex>0</tex> до <tex>k-1</tex>).
Мы не сможем использовать здесь в точности тот же алгоритм, что и для сортировки подсчетом обычных целых чисел, потому что в наборе могут быть различные структуры, имеющие одинаковые ключи. Существует два способа справиться с этой проблемой {{---}} использовать списки для хранения структур в отсортированном массиве или заранее посчитать количество структур с одинаковыми ключами для каждого значения ключа.
=== Подсчет числа различных ключей ======= Описание ====
Исходная последовательность из <tex>n</tex> структур хранится в массиве <tex>A</tex>, а отсортированная {{---}} в массиве <tex>B</tex> того же размера. Кроме того, используется вспомогательный массив <tex>P</tex> с индексами от <tex>0</tex> до <tex>k-1</tex>.
Таким образом после завершения алгоритма в <tex>B</tex> будет содержаться исходная последовательность в отсортированном виде (так как блоки расположены по возрастанию соответствующих ключей).
Стоит также отметить, что эта сортировка является устойчивой, так как два элемента с одинаковыми ключами будут добавлены в том же порядке, в каком просматривались в исходном массиве <tex>A</tex>. ==== Псевдокод ====Благодаря этому свойству существует [[цифровая сортировка]].
=== Псевдокод ===
Здесь <tex>A</tex> и <tex>B</tex> {{---}} массивы структур размера <tex>n</tex>, с индексами от <tex>0</tex> до <tex>n-1</tex>.
<tex>P</tex> {{---}} целочисленный массив размера <tex>k</tex>, с индексами от <tex>0</tex> до <tex>k-1</tex>, где <tex>k</tex> {{---}} количество различных ключей.
копируется структура <tex>A[i]</tex> целиком, а не только её ключ.
=== Анализ ===Весь <!-- Переписать первый абзац -->В первом алгоритме первые два цикла работают за <tex>\Theta(k)</tex> и <tex>\Theta(n)</tex>, соответственно; двойной цикл за <tex>\Theta(n + k)</tex>. Алгоритм имеет линейную временную трудоёмкость <tex>\Theta(n + k)</tex>. Используемая дополнительная память равна <tex>\Theta(k)</tex>. Второй алгоритм состоит из двух проходов по массиву <tex>A</tex> размера <tex>n</tex> и одного прохода по массиву <tex>P</tex> размера <tex>k</tex>.Его трудоемкость, таким образом, равна <tex> O\Theta(n + k)</tex>. На практике сортировку подсчетом имеет смысл применять, если <tex>k = O(n)</tex>, поэтому можно считать время работы алгоритма равным <tex> O\Theta(n)</tex>. <br>Как и в обычной сортировке подсчетом, требуется <tex> O\Theta(n + k)</tex> дополнительной памяти {{---}} на хранение массива <tex>B</tex> размера <tex>n</tex> и массива <tex>P</tex> размера <tex>k</tex>. == Поиск диапазона ключей ==Если диапазон значений не известен заранее, то его можно найти с помощью линейного поиска минимума и максимума в исходном массиве, что не повлияет на асимптотику алгоритма. <br>Нужно учитывать, что минимум может быть отрицательным, в то время как в массиве <tex>P</tex> индексы от <tex>0</tex> до <tex>k-1</tex>. Поэтому при работе с массивом <tex>P</tex> из исходного <tex>A[i]</tex> необходимо вычитать минимум, а при обратной записи в <tex>B[i]</tex> прибавлять его.
== Источники ==
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. «Алгоритмы. Построение и анализ» {{---}} «Вильямс», 2011 г. {{---}} 1296 стр. {{---}} ISBN 978-5-8459-0857-5, 5-8459-0857-4, 0-07-013151-1* [http://ru.wikipedia.org/wiki/Сортировка_подсчётом Сортировка подсчетом Википедия {{---}} ВикипедияСортировка подсчетом]* [http://en.wikipedia.org/wiki/Counting_sort Wikipedia {{---}} Counting sort ]* Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 224{{---}} Wikipedia]226.
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]
