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