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