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