101
правка
Изменения
Новое разбиение на разделы, псевдокод, анализ
{{В разработке}}
== Постановка задачи ==
Иногда бывает очень желательно применить быстрый алгоритм [[Сортировка подсчетом|сортировки подсчетом]] для упорядочивания набора каких-либо "сложных" данных. Под "сложными объектами" здесь подразумеваются структуры, содержащие в себе несколько полей. Одно из них мы выделим и назовем ключом, сортировка будет идти именно по нему (предполагается, что значения, принимаемые ключом - целые числа в диапазоне от <tex>0</tex> до <tex>k-1</tex>).
== Подсчет числа различных ключей ==
=== Описание ===
Здесь исходная последовательность из <tex>n</tex> структур хранится в массиве <tex>A</tex>, а отсортированная - в массиве <tex>B</tex> того же размера. Кроме того используется вспомогательный массив <tex>P</tex> с индексами от <tex>0</tex> до <tex>k-1</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>k</tex> - количество различных ключей), с индексами от <tex>0</tex> до <tex>k-1</tex>. <tex>i</tex>, <tex>carry</tex>, <tex>temporary</tex> {{---}} целочисленные переменные. ComplexCountingSort 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; carry = 0; for i = 0 to k - 1 temporary = P[i]; P[i] = carry; carry = carry + P[i]; for i = 0 to length[A] - 1 B[P[A[i].key]] = A[i]; P[A[i].key] = P[A[i].key] + 1; Здесь шаги 3 и 4 из описания объединены в один цикл.Обратите внимание, что в последнем цикле инструкцией B[P[A[i].key]] = A[i];копируется структура <tex>A[i]</tex> целиком, а не только её ключ. === Анализ ===Весь алгоритм состоит из двух проходов по массиву <tex>A</tex> размера <tex>n</tex> и одного прохода по массиву <tex>P</tex>, размера <tex>k</tex>.Его трудоемкость, таким образом, равна <tex> O(n + k)</tex>. На практике сортировку подсчетом имеет смысл применять, если <tex>k</tex> значительно меньше <tex>n</tex>, поэтому можно считать время работы алгоритма равным <tex> O(n)</tex>.Как и в обычной сортировке подсчетом, алгоритму требуется <tex> O(n + k)</tex> дополнительной памяти. ==Источники==
* [http://ru.wikipedia.org/wiki/Сортировка_подсчётом Википедия {{---}} Сортировка подсчетом]
* [http://en.wikipedia.org/wiki/Counting_sort Wikipedia {{---}} Counting sort]
