277
правок
Изменения
Нет описания правки
'''Сортировка подсчётом''' {{---}} алгоритм сортировки, целых чисел в котором предполагается, что все сортируемые элементы {{---}} целые числа, принадлежащие интервалу диапазоне от <tex>0</tex> до некоторой константы <tex>k</tex>, где <tex>k</tex> {{---}} некоторая целая константаработающий за линейное время.
== Основная идея ==
Основная идея сортировки подсчетом заключается состоит в том, чтобы для каждого элемента <tex>x</tex> определить входного массива подсчитать количество элементов, которые меньше меньших данного. Эта информация будет указывать на позиции элементов в отсортированном массиве. Например, если для элемента <tex>x</tex>. С помощью этого, мы можем поместить элемент туда, где он должен находиться в отсортированном массиве. Например, если есть количество таких элементов будет <tex>42</tex> элемента, которые меньше то <tex>x</tex>, то после сортировки он будет занимать <tex>43</tex>-ю позициюв отсортированном массиве. Если допускается, что несколько элементов элементы могут иметь одинаковое значениеодинаковые значения, то необходимо модифицировать алгоритм придётся модифицировать, потому что мы не можем так как нельзя разместить все такие элементы в одной позиции. Использование сортировки подсчётом целесообразно, когда диапазон возможных значений входных данных достаточно мал по сравнению с количеством элементов в сортируемом множестве, например, миллион натуральных чисел меньших <tex>1000</tex>. Эффективность алгоритма падает, когда необходимо сортировать различные элементы, попавшие в одну ячейкупозицию.
== Простой алгоритм ==
В первом алгоритме первые два цикла работают за <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>.
== Источники ==
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:СортировкиСортировка]]
