105
правок
Изменения
м
== Простой алгоритм ==* Последовательно пройдём по массиву <tex>A</tex> и запишем в <tex>C[i]</tex> количество чисел, равных <tex>i</tex>.
Это простейший вариант алгоритма. Создать вспомогательный массив <tex>C[0..k - 1]</tex>, состоящий из нулей, затем последовательно прочитать элементы входного массива <tex>A</tex>, для каждого <tex>A[i]</tex> увеличить <tex>C[A[i]]</tex> на единицу. * Теперь достаточно пройти по массиву <tex>C</tex>, и для каждого <tex>j number \in \{0, ..., \mathrm k - 1\}</tex> в массив <tex>A</tex> последовательно записать число <tex>jnumber\</tex> <tex> C[jnumber]</tex> раз. === Псевдокод ===
SimpleCountingSort'''function''' simpleCountingSort(A: '''int[n]'''): '''for i ''' number = 0 '''to ''' k - 1 C[inumber] = 0; '''for ''' i = 0 '''to ''' n - 1 C[A[i]] = C[A[i]] + 1; b pos = 0; '''for j ''' number = 0 '''to ''' k - 1 '''for ''' i = 0 '''to ''' C[jnumber] - 1 A[bpos] = jnumber; b pos = b pos + 1;
== Устойчивый алгоритм ==Идея алгоритма состоит в предварительном подсчете количества элементов с различными ключами в исходном массиве и разделении результирующего массива на части соответствующей длины (будем называть их блоками). Затем при повторном проходе исходного массива каждый его элемент копируется в специально отведенный его ключу блок, в первую свободную ячейку. Это осуществляется с помощью массива индексов <tex>P</tex>, в котором хранятся индексы начала блоков для различных ключей. <tex>P[key]</tex> {{---}} индекс в результирующем массиве, соответствующий первому элементу блока для ключа <tex>key</tex>.
В этом варианте помимо входного массива * Пройдем по исходному массиву <tex>A</tex> потребуется два вспомогательных массива — и запишем в <tex>CP[0i]</tex> количество структур, ключ которых равен <tex>i</tex>.[[Файл:Building_P.png]] * Мысленно разобьем массив <tex>B</tex> на <tex>k - </tex> блоков, длина каждого из которых равна соответственно <tex>P[0]</tex>, <tex>P[1]</tex> для счётчика и , ..., <tex>P[k]</tex>B.[[0Файл:Splitting_B_w_colors.png]] * Теперь массив <tex>P</tex> нам больше не нужен.n Превратим его в массив, хранящий в <tex>P[i]</tex> сумму элементов от <tex>0</tex> до <tex>i- 1]</tex> для отсортированного старого массива<tex>P</tex>. [[Файл:P_after_adding. Сначала следует заполнить png]] * Теперь "сдвинем" массив <tex>CP</tex> на элемент вперед: в новом массиве <tex>P[0] = 0</tex> нулями, и а для каждого <tex>A[i]> 0</tex> увеличить <tex>CP[Ai] = P_{old}[i-1]]</tex> на 1, где <tex>P_{old}</tex> {{---}} старый массив <tex>P</tex>. Далее подсчитывается число элементов меньше или равных текущему<br> Это можно сделать за один проход по массиву <tex>P</tex>, причем одновременно с предыдущим шагом. Для <br> После этого каждый действия в массиве <tex>CP</tex> будут хранится индексы массива <tex>B</tex>. <tex>P[jkey]</tex> указывает на начало блока в <tex>B</tex>, начиная с соответствующего ключу <tex>key</tex>C.[[1Файл:P_as_array_of_pointers.png]] * Произведем саму сортировку. Еще раз пройдем по исходному массиву <tex>A</tex>, увеличивают на и для всех <tex>Ci \in [j 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>B[C[A[i].key</tex> {{---}} это ключ структуры, находящейся в массиве <tex>A</tex> на <tex>i</tex>-том месте. [[Файл:Sorting_A.png]] Таким образом после завершения алгоритма в <tex>B</tex> записывается будет содержаться исходная последовательность в отсортированном виде (так как блоки расположены по возрастанию соответствующих ключей). Стоит также отметить, что эта сортировка является устойчивой, так как два элемента с одинаковыми ключами будут добавлены в том же порядке, в каком просматривались в исходном массиве <tex>A</tex>. Благодаря этому свойству существует [i[цифровая сортировка]]. === Псевдокод ===Здесь <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 ''' i = 0 '''to ''' k - 1 CP[i] = 0; '''for ''' i = 0 '''to n ''' length[A] - 1 CP[A[i].key] = CP[A[i].key] + 1; carry = 0; '''for j ''' i = 1 0 '''to ''' k - 1 Ctemporary = P[ji] = C; P[ji] = carry; carry = carry + C[j - 1]temporary; '''for ''' i = n 0 '''to''' length[A] - 1 to 0 CB[P[A[i].key]] = C[A[i]] - 1; B[CP[A[i]].key] = P[A[i].key] + 1;
Если диапазон значений Второй алгоритм состоит из двух проходов по массиву <tex>A</tex> размера <tex>n</tex> и одного прохода по массиву <tex>P</tex> размера <tex>k</tex>.Его трудоемкость, таким образом, равна <tex>\Theta(n + k)</tex>. На практике сортировку подсчетом имеет смысл применять, если <tex>k = O(min и maxn) заранее не известен</tex>, поэтому можно воспользоваться линейным поиском min считать время работы алгоритма равным <tex>\Theta(n)</tex>. <br>Как и maxв обычной сортировке подсчетом, что не повлияет требуется <tex>\Theta(n + k)</tex> дополнительной памяти {{---}} на асимптотику алгоритма. При работе с массивом хранение массива <tex>B</tex> размера <tex>n</tex> и массива <tex>CP</tex> из размера <tex>A[i]k</tex> необходимо вычитать min, а при обратной записи прибавлять. == Анализ ==
В первом алгоритме первые два цикла работают Алгоритм работает за <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>но является псевдополиномиальным.
Дмитрий Мурзин переименовал страницу Сортировка подсчетом в Сортировка подсчётом: Ёфикация
'''Сортировка подсчётом''' — (англ. ''counting sort'') {{---}} алгоритм сортировкицелых чисел в диапазоне от <tex>0</tex> до некоторой константы <tex>k</tex> или сложных объектов, в котором используется диапазон работающий за линейное время.== Сортировка целых чисел сортируемого массива или списка для подсчёта совпадающих элементов==Это простейший вариант алгоритма. Применение сортировки подсчётом целесообразно лишь тогда=== Описание ===Исходная последовательность чисел длины <tex>n</tex>, когда сортируемые числа имеют (или их можно отобразить а в) диапазон возможных значенийконце отсортированная, который достаточно мал по сравнению хранится в массиве <tex>A</tex>. Также используется вспомогательный массив <tex>C</tex> с сортируемым множеством, например, миллион натуральных чисел меньших 1000. Эффективность алгоритма падает, если при попадании нескольких различных элементов в одну ячейкуиндексами от <tex>0</tex> до <tex>\mathrm k - 1</tex>, их надо дополнительно сортироватьизначально заполняемый нулями.
<code>
</code>
== Сортировка сложных объектов ==
Сортировка целых чисел за линейное время это хорошо, но недостаточно. Иногда бывает очень желательно применить быстрый алгоритм [[#Сортировка целых чисел|сортировки подсчетом]] для упорядочивания набора каких-либо "сложных" данных. Под "сложными объектами" здесь подразумеваются структуры, содержащие в себе несколько полей. Одно из них мы выделим и назовем ключом, сортировка будет идти именно по нему (предполагается, что значения, принимаемые ключом {{---}} целые числа в диапазоне от <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>.
<code>
</code>
Здесь шаги 3 и 4 из описания объединены в один цикл.
Обратите внимание, что в последнем цикле инструкцией
B[P[A[i].key]] = A[i];
копируется структура <tex>A[i]</tex> целиком, а не только её ключ.
== Обобщение на произвольный целочисленный диапазон Анализ ==В первом алгоритме первые два цикла работают за <tex>\Theta(k)</tex> и <tex>\Theta(n)</tex>, соответственно; двойной цикл за <tex>\Theta(n + k)</tex>. Алгоритм имеет линейную временную трудоёмкость <tex>\Theta(n + k)</tex>. Используемая дополнительная память равна <tex>\Theta(k)</tex>.
== Поиск диапазона ключей ==
Если диапазон значений не известен заранее, то его можно найти с помощью линейного поиска минимума и максимума в исходном массиве, что не повлияет на асимптотику алгоритма. <br>
Нужно учитывать, что минимум может быть отрицательным, в то время как в массиве <tex>P</tex> индексы от <tex>0</tex> до <tex>k-1</tex>. Поэтому при работе с массивом <tex>P</tex> из исходного <tex>A[i]</tex> необходимо вычитать минимум, а при обратной записи в <tex>B[i]</tex> прибавлять его.
== Ссылки Источники информации ==* [http://ru.wikipedia.org/wiki/Сортировка_подсчётом Сортировка подсчетом {{---}} Википедия]* [http://en.wikipedia.org/wiki/Counting_sort Counting sort {{---}} Wikipedia]* Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 224{{---}}226.
[http[Категория://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%BF%D0%BE%D0%B4%D1%81%D1%87%D1%91%D1%82%D0%BE%D0%BC ВикипедияДискретная математика и алгоритмы]][[Категория: Сортировка подсчетомСортировки]][[Категория: Другие сортировки]]
