277
правок
Изменения
м
→Основная идея
== Основная идея ==
Основная идея состоит в том, чтобы для каждого элемента входного массива, подсчитать количество элементов, меньших данного. Эта информация будет указывать на позиции элементов в отсортированном массиве. Например, если для элемента <tex>x</tex> количество таких элементов будет <tex>42</tex>, то <tex>x</tex> будет занимать <tex>43</tex>-ю позицию в отсортированном массиве. Если элементы могут иметь одинаковые значения, то необходимо модифицировать алгоритм, так как нельзя разместить все такие элементы в одну позицию.
Использование сортировки подсчётом целесообразно, когда диапазон возможных значений входных данных достаточно мал по сравнению с количеством элементов в сортируемом множестве, например, миллион натуральных чисел меньших <tex>1000</tex>. Эффективность алгоритма падает, когда необходимо сортировать различные элементы, попавшие в одну ячейку.
