Изменения

'''Сортировка подсчётом''' — {{---}} алгоритм сортировки, в котором предполагается, что все <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>1000</tex>. Эффективность алгоритма падает, когда необходимо сортировать различные элементы, попавшие в одну ячейку.

[[Категория:СортировкиСортировка]]