Сортировка подсчетом сложных объектов — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (добавлены категории)
Строка 24: Строка 24:
 
* [http://en.wikipedia.org/wiki/Counting_sort Wikipedia | Count_sort]
 
* [http://en.wikipedia.org/wiki/Counting_sort Wikipedia | Count_sort]
 
* Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 224-226.
 
* Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 224-226.
 +
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Сортировки]]

Версия 21:28, 7 мая 2012

Постановка задачи

Иногда надо отсортировать набор каких либо "сложных" данных, например, структур, в которых несколько полей, и сортировать надо по одному из них. В данном случае для сортировки подсчетом предполагается, что величины, хранящиеся в данных ключах, являются целыми числами от 0 до k - 1.

Мы будем использовать все тот же алгоритм, что и для обыкновенных целых чисел, но с небольшой модификацией. Она необходима для разрешения следующей проблемы: разные структуры могут иметь одинаковые ключи. Нам надо каким-либо образом это учитывать.

Решение

Пусть далее исходня последовательность из n структур хранится в массиве С, а отсортированная - в А, причем ее ключи принадлежат множеству 0..k.

В качестве модификации можно сделать из каждой ячейки массива А список, в который будем добавлять структуры с одинаковыми ключами. Однако, этот вариант плох тем, что надо поддерживать сам список, что не является самым простым решением. К тому же нам надо будет хранить дополнительную информацию в виде ссылок на следующий элемент в списке.

Избавиться от этих недостатков можно следующим образом.

MassA.png

  • Подсчитаем количество разных ключей в списке (пусть их будет k), а также количество ключей каждого вида. Пусть массив Р[i] содержит количество ключей, равных i. Очевидно, что это делается за О(n).
  • Разобьем массив А на k блоков, длина каждого из которых равна соотв. P[1], P[2], ..., P[k], и поставим над первым элементом каждого блока по указателю point_i, который в дальнейшем будет указывать на первый свободный элемент в своем блоке i.
  • Теперь массив Р нам больше не нужен. Тогда превратим его в массив, хранящий в Р[i] - сумму элементов от 0 до i - 1 старого массива Р. Это делается за один пробег по массиву.
  • Теперь собственно сортировка. Для определения на очередном шаге по массиву С, куда вставить текущий элемент посмотрим на поле key и запишем эту структурку в [math]A[P[key] + point_{key}][/math]. Затем увеличим соотв. значение указателя на 1. Таким образом после завершения алгоритма в А будет содержаться наша последовательность в отсортированном виде (так как блоки расположены по возрастанию соотв. ключей).

Стоит также отметить, что эта сортировка устойчивая, так как два элемента с одинаковыми ключами будут добавлены в том же порядке, в котором просматривались в изначальном массиве.

Источники

  • Wikipedia | Count_sort
  • Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 224-226.