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