Изменения

'''Сортировка подсчётом''' (англ. ''counting sort'') {{---}} алгоритм сортировки, целых чисел в котором предполагается, что все сортируемые элементы {{---}} целые числа, принадлежащие интервалу диапазоне от <tex>0</tex> до некоторой константы <tex>k</tex>или сложных объектов, где работающий за линейное время.== Сортировка целых чисел ==Это простейший вариант алгоритма.=== Описание ===Исходная последовательность чисел длины <tex>n</tex>, а в конце отсортированная, хранится в массиве <tex>A</tex>. Также используется вспомогательный массив <tex>C</tex> с индексами от <tex>0</tex> до <tex>\mathrm k- 1</tex> {{---}} некоторая целая константа, изначально заполняемый нулями.

== Основная идея ==Основная идея сортировки подсчетом заключается в том, чтобы для каждого элемента <tex>x</tex> определить количество элементов, которые меньше * Последовательно пройдём по массиву <tex>xA</tex>. С помощью этого, мы можем поместить элемент туда, где он должен находиться и запишем в отсортированном массиве. Например, если есть <tex>42C[i]</tex> элементаколичество чисел, которые меньше равных <tex>xi</tex>, то после сортировки он будет занимать <tex>43</tex>-ю позицию. Если допускается, что несколько элементов могут иметь одинаковое значение, то алгоритм придётся модифицировать, потому что мы не можем разместить все такие элементы в одной позиции.

Использование сортировки подсчётом целесообразно, когда диапазон возможных значений входных данных * Теперь достаточно мал пройти по сравнению с количеством элементов в сортируемом множестве, например, миллион натуральных чисел меньших массиву <tex>1000C</tex>и для каждого <tex>number \in \{0, ... Эффективность алгоритма падает, когда необходимо сортировать различные элементы, попавшие \mathrm k - 1\}</tex> в одну ячейкумассив <tex>A</tex> последовательно записать число <tex>number\</tex> <tex> C[number]</tex> раз.

== Простой алгоритм = Псевдокод ===Это простейший вариант алгоритма. Создать вспомогательный массив <tex>C[0..k - 1]</tex>, состоящий из нулей, затем последовательно прочитать элементы входного массива <tex>A</tex> и для каждого <tex>A[i]</tex> увеличить <tex>C[A[i]]</tex> на единицу. Теперь достаточно пройти по массиву <tex>C</tex> и для каждого <tex>number \in \{0, ..., k - 1\}</tex> в массив <tex>A</tex> последовательно записать число <tex>number\</tex> <tex> C[number]</tex> раз.

SimpleCountingSort'''function''' simpleCountingSort(A: '''int[n]'''): '''for ''' number = 0 '''to ''' k - 1 C[number] = 0; '''for ''' i = 0 '''to length[A] ''' n - 1 C[A[i]] = C[A[i]] + 1;

'''for ''' number = 0 '''to ''' k - 1 '''for ''' i = 0 '''to ''' C[jnumber] - 1

== Устойчивый алгоритм Сортировка сложных объектов ==В этом варианте помимо входного массива Сортировка целых чисел за линейное время это хорошо, но недостаточно. Иногда бывает очень желательно применить быстрый алгоритм [[#Сортировка целых чисел|сортировки подсчетом]] для упорядочивания набора каких-либо "сложных" данных. Под "сложными объектами" здесь подразумеваются структуры, содержащие в себе несколько полей. Одно из них мы выделим и назовем ключом, сортировка будет идти именно по нему (предполагается, что значения, принимаемые ключом {{---}} целые числа в диапазоне от <tex>A0</tex> потребуется два вспомогательных массива — до <tex>C[0..\mathrm k - 1]</tex> ). Мы не сможем использовать здесь в точности тот же алгоритм, что и для счётчика и сортировки подсчетом обычных целых чисел, потому что в наборе могут быть различные структуры, имеющие одинаковые ключи. Существует два способа справиться с этой проблемой {{---}} использовать списки для хранения структур в отсортированном массиве или заранее посчитать количество структур с одинаковыми ключами для каждого значения ключа.  === Описание ===Исходная последовательность из <tex>n</tex> структур хранится в массиве <tex>A</tex>, а отсортированная {{---}} в массиве <tex>B[</tex> того же размера. Кроме того, используется вспомогательный массив <tex>P</tex> с индексами от <tex>0</tex> до <tex>\mathrm k-1</tex>. Идея алгоритма состоит в предварительном подсчете количества элементов с различными ключами в исходном массиве и разделении результирующего массива на части соответствующей длины (будем называть их блоками). Затем при повторном проходе исходного массива каждый его элемент копируется в специально отведенный его ключу блок, в первую свободную ячейку.n - 1]Это осуществляется с помощью массива индексов <tex>P</tex> , в котором хранятся индексы начала блоков для отсортированного массиваразличных ключей. Сначала следует заполнить массив <tex>CP[key]</tex> нулями{{---}} индекс в результирующем массиве, и соответствующий первому элементу блока для каждого ключа <tex>key</tex>.  * Пройдем по исходному массиву <tex>A</tex> и запишем в <tex>P[i]</tex> увеличить количество структур, ключ которых равен <tex>i</tex>C. [A[iФайл:Building_P.png]] * Мысленно разобьем массив <tex>B</tex> на <tex>k</tex> блоков, длина каждого из которых равна соответственно <tex>P[0]</tex>, <tex>P[1]</tex>, .. Далее подсчитывается число элементов меньше или равных текущему. Для этого каждый , <tex>CP[numberk]</tex>.[[Файл:Splitting_B_w_colors.png]] * Теперь массив <tex>P</tex> нам больше не нужен. Превратим его в массив, начиная с хранящий в <tex>CP[i]</tex> сумму элементов от <tex>0</tex> до <tex>i-1</tex> старого массива <tex>P</tex>. [[Файл:P_after_adding.png]] * Теперь "сдвинем" массив <tex>P</tex> на элемент вперед: в новом массиве <tex>P[0] = 0</tex>, увеличивают на а для <tex>i > 0</tex> <tex>CP[i] = P_{old}[number i- 1]</tex>, где <tex>P_{old}</tex> {{---}} старый массив <tex>P</tex>. На последнем шаге алгоритма читается входной массив <br> Это можно сделать за один проход по массиву <tex>P</tex>, причем одновременно с конца и предыдущим шагом. <br> После этого действия в каждый массиве <tex>P</tex> будут хранится индексы массива <tex>B</tex>. <tex>P[Ckey]</tex> указывает на начало блока в <tex>B</tex>, соответствующего ключу <tex>key</tex>.[[Файл:P_as_array_of_pointers.png]] * Произведем саму сортировку. Еще раз пройдем по исходному массиву <tex>A</tex> и для всех <tex>i \in [0, n-1]</tex> будем помещать структуру <tex>A[i]]]</tex> записывается в массив <tex>B</tex> на место <tex>P[A[i].key]</tex>, а значение затем увеличивать <tex>CP[A[i].key]</tex> уменьшается на <tex>1</tex>. Здесь <tex>A[i].key</tex> {{---}} это ключ структуры, находящейся в массиве <tex>A</tex> на <tex>i</tex>-том месте. [[Файл:Sorting_A.png]] Таким образом после завершения алгоритма в <tex>B</tex> будет содержаться исходная последовательность в отсортированном виде (так как блоки расположены по возрастанию соответствующих ключей). Алгоритм устойчив Стоит также отметить, что эта сортировка является устойчивой, так как два элемента с одинаковыми ключами будут добавлены в том же порядке, в каком просматривались в исходном массиве <tex>A</tex>. Устойчивость может потребоваться при Благодаря этому свойству существует [[Сортировка_подсчетом_сложных_объектов|сортировке сложных структур данныхцифровая сортировка]]. === Псевдокод ===Здесь <tex>A</tex> и <tex>B</tex> {{---}} массивы структур размера <tex>n</tex>, с индексами от <tex>0</tex> до <tex>n-1</tex>.<tex>P</tex> {{---}} целочисленный массив размера <tex>k</tex>, с индексами от <tex>0</tex> до <tex>k-1</tex>, где <tex>k</tex> {{---}} количество различных ключей.

StableCountingSort'''function''' complexCountingSort(A: '''int[n]''', B: '''int[n]'''): '''for number ''' i = 0 '''to ''' k - 1 CP[numberi] = 0; '''for ''' i = 0 '''to ''' length[A] - 1 CP[A[i].key] = CP[A[i].key] + 1; carry = 0; '''for number ''' i = 1 0 '''to ''' k - 1 Ctemporary = P[ji] = C; P[ji] = carry; carry = carry + C[j - 1]temporary; '''for ''' i = 0 '''to''' length[A] - 1 to 0 B[CP[A[i].key]] = A[i]; CP[A[i].key] = CP[A[i].key] - + 1;

== Обобщение на произвольный целочисленный диапазон Анализ ==Если диапазон значений В первом алгоритме первые два цикла работают за <tex>\Theta(min k)</tex> и max<tex>\Theta(n) заранее не известен</tex>, можно воспользоваться линейным поиском min и max, что не повлияет на асимптотику алгоритмасоответственно; двойной цикл за <tex>\Theta(n + k)</tex>. При работе с массивом Алгоритм имеет линейную временную трудоёмкость <tex>C\Theta(n + k)</tex> из . Используемая дополнительная память равна <tex>A[i]\Theta(k)</tex> необходимо вычитать min, а при обратной записи прибавлять.

== Анализ ==В первом алгоритме первые два цикла работают за Второй алгоритм состоит из двух проходов по массиву <tex>A</tex> размера <tex>\Theta(k)n</tex> и одного прохода по массиву <tex>\Theta(n)P</tex> размера <tex>k</tex>.Его трудоемкость, таким образом, соответственно; двойной цикл за равна <tex>\Theta(n + k)</tex>. Во втором алгоритме циклы занимают На практике сортировку подсчетом имеет смысл применять, если <tex>\Thetak = O(kn)</tex>, поэтому можно считать время работы алгоритма равным <tex>\Theta(n)</tex>. <br>Как и в обычной сортировке подсчетом, требуется <tex>\Theta(n + k)</tex> и дополнительной памяти {{---}} на хранение массива <tex>\Theta(n)B</tex>, соответственно. Итого оба алгоритма имеют линейную временную трудоёмкость размера <tex>\Theta(n + k)</tex>. Используемая память в первом алгоритме равна и массива <tex>\Theta(k)P</tex>, а во втором размера <tex>\Theta(n + k)</tex>. Алгоритм работает за линейное время, но является псевдополиномиальным.

На практике сортировка подсчетом применяется== Поиск диапазона ключей ==Если диапазон значений не известен заранее, то его можно найти с помощью линейного поиска минимума и максимума в исходном массиве, когда что не повлияет на асимптотику алгоритма. <br>Нужно учитывать, что минимум может быть отрицательным, в то время как в массиве <tex>P</tex> индексы от <tex>0</tex> до <tex>k = O(n)-1</tex>. Поэтому при работе с массивом <tex>P</tex> из исходного <tex>A[i]</tex> необходимо вычитать минимум, а при обратной записи в этом случае время работы алгоритма равно <tex>\Theta(n)B[i]</tex>прибавлять его.

== Источники информации ==* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. «Алгоритмы. Построение и анализ» {{---}} «Вильямс», 2011 г. {{---}} 1296 стр. {{---}} ISBN 978-5-8459-0857-5, 5-8459-0857-4, 0-07-013151-1

[[Категория:Дискретная математика и алгоритмы]][[Категория:Сортировки]][[Категория: Другие сортировки]]