277
правок
Изменения
Нет описания правки
'''Сортировка подсчётом''' — алгоритм сортировки, в котором используется диапазон чисел сортируемого массива или списка для подсчёта совпадающих предполагается, что все <tex>n</tex> входных элементов. Применение сортировки подсчётом целесообразно лишь тогда, когда сортируемые {{---}} целые числа имеют (или их можно отобразить в) диапазон возможных значений, который достаточно мал по сравнению с сортируемым множествомпринадлежащие интервалу от <tex>0</tex> до <tex>k</tex>, напримергде <tex>k</tex> {{---}} некоторая целая константа. Например, миллион натуральных чисел меньших <tex>1000</tex>. Эффективность алгоритма падает, если при попадании нескольких различных элементов в одну ячейку, их надо дополнительно сортировать. == Основная идея ==Основная идея сортировки подсчетом заключается в том, чтобы для каждого входного элемента <tex>x</tex> определить количество элементов, которые меньше <tex>x</tex>. C помощью этой информации элемент <tex>x</tex> можно разместить на той позиции выходного массива, где он должен находиться. Например, если всего имеется <tex>42</tex> элемента, которые меньше <tex>x</tex>, то в выходной последовательности элемент <tex>x</tex> должен заниматься <tex>43</tex>-ю позицию. Если допускается ситуация, когда несколько элементов имеют одно и тоже значение, то эту схему придётся модифицировать, так как мы не можем разместить все такие элементы в одной позиции.
== Простой алгоритм ==
Это простейший вариант алгоритма. Создать вспомогательный массив <tex>C[0..k - 1]</tex>, состоящий из нулей, затем последовательно прочитать элементы входного массива <tex>A</tex>, и для каждого <tex>A[i]</tex> увеличить <tex>C[A[i]]</tex> на единицу. Теперь достаточно пройти по массиву <tex>C</tex>, и для каждого <tex>j number \in \{0, ..., k - 1\}</tex> в массив <tex>A</tex> последовательно записать число <tex>jnumber\</tex> <tex> C[jnumber]</tex> раз.
<code>
SimpleCountingSort
for i number = 0 to k - 1 C[inumber] = 0; for i = 0 to n length[A] - 1
C[A[i]] = C[A[i]] + 1;
for i = 0 to C[j] - 1
A[bpos] = jnumber; b pos = b pos + 1;
</code>
== Устойчивый алгоритм ==
В этом варианте помимо входного массива <tex>A</tex> потребуется два вспомогательных массива — <tex>C[0..k - 1]</tex> для счётчика и <tex>B[0..n - 1]</tex> для отсортированного массива. Сначала следует заполнить массив <tex>C</tex> нулями, и для каждого <tex>A[i]</tex> увеличить <tex>C[A[i]]</tex> на 1. Далее подсчитывается число элементов меньше или равных текущему. Для этого каждый <tex>C[jnumber]</tex>, начиная с <tex>C[1]</tex>, увеличивают на <tex>C[j number - 1]</tex>. На последнем шаге алгоритма читается входной массив с конца, значение и в каждый <tex>B[C[A[i]]]</tex> уменьшается на 1 и в каждый записывается <tex>B[C[A[i]]]</tex> записывается , а значение <tex>C[A[i]]</tex>уменьшается на 1. Алгоритм устойчив. Устойчивость может потребоваться при [[Сортировка_подсчетом_сложных_объектов|сортировке сложных структур данных]].
<code>
StableCountingSort
for i number = 0 to k - 1 C[inumber] = 0; for i = 0 to n length[A] - 1
C[A[i]] = C[A[i]] + 1;
for j number = 1 to k - 1
C[j] = C[j] + C[j - 1];
for i = n length[A] - 1 to 0 B[C[A[i]]] = A[i];
C[A[i]] = C[A[i]] - 1;
</code>
== Обобщение на произвольный целочисленный диапазон ==
Если диапазон значений (min и max) заранее не известен, можно воспользоваться линейным поиском min и max, что не повлияет на асимптотику алгоритма. При работе с массивом <tex>C</tex> из <tex>A[i]</tex> необходимо вычитать min, а при обратной записи прибавлять.
== Анализ ==
В первом алгоритме первые два цикла работают за <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>k = O(n)</tex>, а в этом случае время работы алгоритма равно <tex>\Theta(n)</tex>
== Ссылки Источники ==* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. «Алгоритмы. Построение и анализ» {{---}} «Вильямс», 2011 г. {{---}} 1296 стр. {{---}} ISBN 978-5-8459-0857-5, 5-8459-0857-4, 0-07-013151-1* [http://ru.wikipedia.org/wiki/Сортировка_подсчётом Сортировка подсчетом {{---}} Википедия]
[http[Категория://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%BF%D0%BE%D0%B4%D1%81%D1%87%D1%91%D1%82%D0%BE%D0%BC ВикипедияДискретная математика и алгоритмы]][[Категория: Сортировка подсчетом]]
