Изменения

'''Сортировка подсчётом''' — алгоритм сортировки, в котором используется диапазон чисел сортируемого массива или списка для подсчёта совпадающих предполагается, что все <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> раз.

for i number = 0 to k - 1 C[inumber] = 0; for i = 0 to n length[A] - 1

b pos = 0; for j number = 0 to k - 1

A[bpos] = jnumber; b pos = b pos + 1;

 В этом варианте помимо входного массива <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. Алгоритм устойчив. Устойчивость может потребоваться при [[Сортировка_подсчетом_сложных_объектов|сортировке сложных структур данных]].

for i number = 0 to k - 1 C[inumber] = 0; for i = 0 to n length[A] - 1

for j number = 1 to k - 1

for i = n length[A] - 1 to 0 B[C[A[i]]] = A[i];