105
правок
Изменения
м
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;
ComplexCountingSort'''function''' complexCountingSort(A: '''int[n]''', B: '''int[n]'''): '''for ''' i = 0 '''to ''' k - 1 P[i] = 0; '''for ''' i = 0 '''to ''' length[A] - 1 P[A[i].key] = P[A[i].key] + 1;
Дмитрий Мурзин переименовал страницу Сортировка подсчетом в Сортировка подсчётом: Ёфикация
'''Сортировка подсчётом''' (англ. ''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>A</tex> и запишем в <tex>C[i]</tex> количество чисел, равных <tex>i</tex>.
* Теперь достаточно пройти по массиву <tex>C</tex> и для каждого <tex>number \in \{0, ..., \mathrm k - 1\}</tex> в массив <tex>A</tex> последовательно записать число <tex>number\</tex> <tex> C[number]</tex> раз.
=== Псевдокод ===
<code>
pos = 0;
'''for ''' number = 0 '''to ''' k - 1 '''for ''' i = 0 '''to ''' C[jnumber] - 1
A[pos] = number;
pos = pos + 1;
== Сортировка сложных объектов ==
Сортировка целых чисел за линейное время это хорошо, но недостаточно. Иногда бывает очень желательно применить быстрый алгоритм [[#Сортировка целых чисел|сортировки подсчетом]] для упорядочивания набора каких-либо "сложных" данных. Под "сложными объектами" здесь подразумеваются структуры, содержащие в себе несколько полей. Одно из них мы выделим и назовем ключом, сортировка будет идти именно по нему (предполагается, что значения, принимаемые ключом {{---}} целые числа в диапазоне от <tex>0</tex> до <tex>\mathrm k-1</tex>).
Мы не сможем использовать здесь в точности тот же алгоритм, что и для сортировки подсчетом обычных целых чисел, потому что в наборе могут быть различные структуры, имеющие одинаковые ключи. Существует два способа справиться с этой проблемой {{---}} использовать списки для хранения структур в отсортированном массиве или заранее посчитать количество структур с одинаковыми ключами для каждого значения ключа.
=== Описание ===
Исходная последовательность из <tex>n</tex> структур хранится в массиве <tex>A</tex>, а отсортированная {{---}} в массиве <tex>B</tex> того же размера. Кроме того, используется вспомогательный массив <tex>P</tex> с индексами от <tex>0</tex> до <tex>\mathrm k-1</tex>.
Идея алгоритма состоит в предварительном подсчете количества элементов с различными ключами в исходном массиве и разделении результирующего массива на части соответствующей длины (будем называть их блоками). Затем при повторном проходе исходного массива каждый его элемент копируется в специально отведенный его ключу блок, в первую свободную ячейку. Это осуществляется с помощью массива индексов <tex>P</tex>, в котором хранятся индексы начала блоков для различных ключей. <tex>P[key]</tex> {{---}} индекс в результирующем массиве, соответствующий первому элементу блока для ключа <tex>key</tex>.
[[Файл:Building_P.png]]
* Мысленно разобьем массив <tex>B</tex> на <tex>k</tex> блоков, длина каждого из которых равна соответственно <tex>P[10]</tex>, <tex>P[21]</tex>, ..., <tex>P[k]</tex>.
[[Файл:Splitting_B_w_colors.png]]
<tex>P</tex> {{---}} целочисленный массив размера <tex>k</tex>, с индексами от <tex>0</tex> до <tex>k-1</tex>, где <tex>k</tex> {{---}} количество различных ключей.
<code>
carry = 0;
'''for ''' i = 0 '''to ''' k - 1
temporary = P[i];
P[i] = carry;
carry = carry + temporary; '''for ''' i = 0 '''to ''' length[A] - 1
B[P[A[i].key]] = A[i];
P[A[i].key] = P[A[i].key] + 1;
Его трудоемкость, таким образом, равна <tex>\Theta(n + k)</tex>. На практике сортировку подсчетом имеет смысл применять, если <tex>k = O(n)</tex>, поэтому можно считать время работы алгоритма равным <tex>\Theta(n)</tex>. <br>
Как и в обычной сортировке подсчетом, требуется <tex>\Theta(n + k)</tex> дополнительной памяти {{---}} на хранение массива <tex>B</tex> размера <tex>n</tex> и массива <tex>P</tex> размера <tex>k</tex>.
Алгоритм работает за линейное время, но является псевдополиномиальным.
== Поиск диапазона ключей ==
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]
[[Категория: Другие сортировки]]
