Редактирование: Сортировка подсчетом сложных объектов

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
#перенаправление [[Сортировка подсчётом#Сортировка сложных объектов]]
+
Иногда надо отсортировать набор каких либо "сложных" данных, например, структур, в которых несколько полей, и сортировать надо по одному из них.
 +
В данном случае для [[Сортировка подсчетом|сортировки подсчетом]] предполагается, что величины, хранящиеся в данных ключах, являются целыми числами от 0 до k - 1.
 +
 
 +
Мы будем использовать все тот же алгоритм, что и для обыкновенных целых чисел, но с небольшой модификацией. Она необходима для разрешения следующей проблемы: разные структуры могут иметь одинаковые ключи. Нам надо каким-либо образом это учитывать.
 +
 
 +
Пусть далее исходня последовательность из n структур хранится в массиве С, а отсортированная - в А, причем ее ключи прина
 +
Как можно модифицировать алгоритм? Например, сделать изкаждой ячейки массива А список, в который будем добавлять структуры с одинаковыми ключами. Однако, этот вариант плох тем, что надо поддерживать сам список, что не является самым простым решением. К тому же нам надо будет хранить дополнительную информацию в виде ссылок на следующий элемент в списке.
 +
 
 +
Избавиться от этих недостатков можно следующим образом.
 +
 
 +
[[Файл:massA.png|800px|]]
 +
 
 +
* Подсчитаем количество разных ключей в списке (пусть их будет k), а также количество ключей каждого вида. Пусть массив Р[i] содержит количество ключей, равных i. Очевидно, что это делается за О(n).
 +
* Пусть для определенности P[1], P[2], ..., P[k] не равны нулю. Тогда разобьем массив А на k блоков, длина каждого из которых равна соотв. P[1], P[2], ..., P[k], и поставим над первым элементом каждого блока по указателю point_i, который в дальнейшем будет указывать на первый свободный элемент в своем блоке i.
 +
* Теперь массив Р нам больше не нужен. Тогда превратим его в массив, хранящий в Р[i] - сумму элементов от 0 до i - 1 старого массива Р. Это делается за один пробег по массиву.
 +
* Теперь собственно сортировка.
 +
Как мы определим на очередном шаге по массиву С, куда вставить текущий элемент? Очень просто. Посмотрим на поле key и запишем эту структурку в A[P[key] + point_key]. Таким образом, после завершения алгоритма в А будет содержаться наша последовательность в отсортированном виде (так как блоки расположены по возрастанию соотв. ключей).
 +
 
 +
Стоит также отметить, что эта сортировка устойчивая, так как два элемента с одинаковыми ключами будут добавлены в том же порядке, в котором просматривались в изначальном массиве.

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)