101
правка
Изменения
Тире вместо дефисов, P вместо B и пояснение перед описанием
== Постановка задачи ==
Иногда бывает очень желательно применить быстрый алгоритм [[Сортировка подсчетом|сортировки подсчетом]] для упорядочивания набора каких-либо "сложных" данных. Под "сложными объектами" здесь подразумеваются структуры, содержащие в себе несколько полей. Одно из них мы выделим и назовем ключом, сортировка будет идти именно по нему (предполагается, что значения, принимаемые ключом {{- --}} целые числа в диапазоне от <tex>0</tex> до <tex>k-1</tex>).
Мы не сможем использовать здесь в точности тот же алгоритм, что и для сортировки подсчетом обычных целых чисел, потому что в наборе могут быть различные структуры, имеющие одинаковые ключи. Существует два способа справиться с этой проблемой {{---}} использовать списки для хранения структур в отсортированном массиве или заранее посчитать количество структур с одинаковыми ключами для каждого значения ключа.
== Использование списков ==
Пусть далее исходная последовательность из <tex>n</tex> структур хранится в массиве <tex>A</tex>, а отсортированная {{- --}} в массиве <tex>P</tex> с индексами от <tex>0</tex> до <tex>k-1</tex>.
Сделаем из каждой ячейки массива <tex>BP</tex> список, в который будем добавлять структуры с одинаковыми ключами.
[[Файл:List_solution.png|500px|]]
== Подсчет числа различных ключей ==
=== Описание ===
Здесь исходная последовательность из <tex>n</tex> структур хранится в массиве <tex>A</tex>, а отсортированная {{- --}} в массиве <tex>B</tex> того же размера. Кроме того используется вспомогательный массив <tex>P</tex> с индексами от <tex>0</tex> до <tex>k-1</tex>. Идея алгоритма состоит в предварительном подсчете количества элементов с различными ключами в исходном массиве и разделении результирующего массива на части соответствующей длины. Затем при повторном проходе исходного массива каждый его элемент копируется в специально отведенный его ключу блок, в первую свободную ячейку. Это осуществляется с помощью массива индексов <tex>P</tex>, в котором хранятся индексы начала блоков для различных ключей. <tex>P[key]</tex> {{---}} индекс в результирующем массиве, соответствующий первому элементу блока для ключа <tex>key</tex>.
* Пройдем по исходному массиву <tex>A</tex> и запишем в <tex>P[i]</tex> количество структур, ключ которых равен <tex>i</tex>.
[[Файл:P_after_adding.png]]
* Теперь "сдвинем" массив <tex>P</tex> на элемент вперед: в новом массиве <tex>P[0] = 0</tex>, а для <tex>i > 0</tex> <tex>P[i] = P_{old}[i-1]</tex>, где <tex>P_{old}</tex> {{- --}} старый массив <tex>P</tex>. <br> Это можно сделать за один проход по массиву <tex>P</tex>, причем одновременно с предыдущим шагом. <br> После этого действия в массиве <tex>P</tex> будут хранится индексы массива <tex>B</tex>. <tex>P[key]</tex> указывает на начало блока в <tex>B</tex>, соответствующего ключу <tex>key</tex>.
[[Файл:P_as_array_of_pointers.png]]
Здесь <tex>A</tex> и <tex>B</tex> {{---}} массивы структур размера <tex>n</tex>, с индексами от <tex>0</tex> до <tex>n-1</tex>.
<tex>P</tex> {{---}} целочисленный массив размера <tex>k</tex> (<tex>k</tex> - количество различных ключей), с индексами от <tex>0</tex> до <tex>k-1</tex>, где <tex>k</tex> {{---}} количество различных ключей. <br> <tex>i</tex>, <tex>carry</tex>, <tex>temporary</tex> {{---}} целочисленные переменные.
ComplexCountingSort
* [http://ru.wikipedia.org/wiki/Сортировка_подсчётом Википедия {{---}} Сортировка подсчетом]
* [http://en.wikipedia.org/wiki/Counting_sort Wikipedia {{---}} Counting sort]
* Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 224{{---}}226.
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]
