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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Анализ)
Строка 1: Строка 1:
== Постановка задачи ==
+
#перенаправление [[Сортировка подсчетом#Сортировка сложных объектов]]
Иногда бывает очень желательно применить быстрый алгоритм [[Сортировка подсчетом|сортировки подсчетом]] для упорядочивания набора каких-либо "сложных" данных. Под "сложными объектами" здесь подразумеваются структуры, содержащие в себе несколько полей. Одно из них мы выделим и назовем ключом, сортировка будет идти именно по нему (предполагается, что значения, принимаемые ключом {{---}} целые числа в диапазоне от <tex>0</tex> до <tex>k-1</tex>).
 
 
 
Мы не сможем использовать здесь в точности тот же алгоритм, что и для сортировки подсчетом обычных целых чисел, потому что в наборе могут быть различные структуры, имеющие одинаковые ключи. Существует два способа справиться с этой проблемой {{---}} использовать списки для хранения структур в отсортированном массиве или заранее посчитать количество структур с одинаковыми ключами для каждого значения ключа. 
 
 
 
== Использование списков ==
 
Сначала расскажем как делать <b>не нужно</b>. <br>
 
Пусть далее исходная последовательность из <tex>n</tex> структур хранится в массиве <tex>A</tex>, а отсортированная {{---}} в массиве <tex>P</tex> с индексами от <tex>0</tex> до <tex>k-1</tex>.
 
 
 
Сделаем из каждой ячейки массива <tex>P</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>P</tex>, в котором хранятся индексы начала блоков для различных ключей. <tex>P[key]</tex> {{---}} индекс в результирующем массиве, соответствующий первому элементу блока для ключа <tex>key</tex>.
 
 
 
* Пройдем по исходному массиву <tex>A</tex> и запишем в <tex>P[i]</tex> количество структур, ключ которых равен <tex>i</tex>.
 
[[Файл:Building_P.png]]
 
 
 
* Мысленно разобьем массив <tex>B</tex> на <tex>k</tex> блоков, длина каждого из которых равна соответственно <tex>P[1]</tex>, <tex>P[2]</tex>, ..., <tex>P[k]</tex>.
 
[[Файл:Splitting_B_w_colors.png]]
 
 
 
* Теперь массив <tex>P</tex> нам больше не нужен. Превратим его в массив, хранящий в <tex>P[i]</tex> сумму элементов от <tex>0</tex> до <tex>i-1</tex> старого массива <tex>P</tex>.
 
[[Файл:P_after_adding.png]]
 
 
 
* Теперь "сдвинем" массив <tex>P</tex> на элемент вперед: в новом массиве <tex>P[0] = 0</tex>, а для <tex>i > 0</tex> <tex>P[i] = P_{old}[i-1]</tex>, где <tex>P_{old}</tex> {{---}} старый массив <tex>P</tex>. <br> Это можно сделать за один проход по массиву <tex>P</tex>, причем одновременно с предыдущим шагом. <br> После этого действия в массиве <tex>P</tex> будут хранится индексы массива <tex>B</tex>. <tex>P[key]</tex> указывает на начало блока в <tex>B</tex>, соответствующего ключу <tex>key</tex>.
 
[[Файл:P_as_array_of_pointers.png]]
 
 
 
* Произведем саму сортировку. Еще раз пройдем по исходному массиву <tex>A</tex> и для всех <tex>i \in [0, n-1]</tex> будем помещать структуру <tex>A[i]</tex> в массив <tex>B</tex> на место <tex>P[A[i].key]</tex>, а затем увеличивать <tex>P[A[i].key]</tex> на <tex>1</tex>. Здесь <tex>A[i].key</tex> {{---}} это ключ структуры, находящейся в массиве <tex>A</tex> на <tex>i</tex>-том месте.
 
[[Файл:Sorting_A.png]]
 
 
 
Таким образом после завершения алгоритма в <tex>B</tex> будет содержаться исходная последовательность в отсортированном виде (так как блоки расположены по возрастанию соответствующих ключей).
 
 
 
Стоит также отметить, что эта сортировка является устойчивой, так как два элемента с одинаковыми ключами будут добавлены в том же порядке, в каком просматривались в исходном массиве <tex>A</tex>.
 
 
 
=== Псевдокод ===
 
 
 
Здесь <tex>A</tex> и <tex>B</tex> {{---}} массивы структур размера <tex>n</tex>, с индексами от <tex>0</tex> до <tex>n-1</tex>.
 
<tex>P</tex> {{---}} целочисленный массив размера <tex>k</tex>, с индексами от <tex>0</tex> до <tex>k-1</tex>, где <tex>k</tex> {{---}} количество различных ключей.
 
ComplexCountingSort
 
    for i = 0 to k - 1
 
        P[i] = 0;
 
       
 
    for i = 0 to length[A] - 1
 
        P[A[i].key] = P[A[i].key] + 1;
 
   
 
    carry = 0;
 
    for i = 0 to k - 1
 
        temporary = P[i];
 
        P[i] = carry;
 
        carry = carry + temporary;
 
   
 
    for i = 0 to length[A] - 1
 
        B[P[A[i].key]] = A[i];
 
        P[A[i].key] = P[A[i].key] + 1;
 
 
 
Здесь шаги 3 и 4 из описания объединены в один цикл.
 
Обратите внимание, что в последнем цикле инструкцией
 
B[P[A[i].key]] = A[i];
 
копируется структура <tex>A[i]</tex> целиком, а не только её ключ.
 
 
 
=== Анализ ===
 
Весь алгоритм состоит из двух проходов по массиву <tex>A</tex> размера <tex>n</tex> и одного прохода по массиву <tex>P</tex> размера <tex>k</tex>.
 
Его трудоемкость, таким образом, равна <tex> O(n + k)</tex>. На практике сортировку подсчетом имеет смысл применять, если <tex>k = O(n)</tex>, поэтому можно считать время работы алгоритма равным <tex> O(n)</tex>. <br>
 
Как и в обычной сортировке подсчетом, требуется <tex> O(n + k)</tex> дополнительной памяти {{---}} на хранение массива <tex>B</tex> размера <tex>n</tex> и массива <tex>P</tex> размера <tex>k</tex>.
 
 
 
== Источники ==
 
* [http://ru.wikipedia.org/wiki/Сортировка_подсчётом Википедия {{---}} Сортировка подсчетом]
 
* [http://en.wikipedia.org/wiki/Counting_sort Wikipedia {{---}} Counting sort]
 
* Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 224{{---}}226.
 
 
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Сортировки]]
 

Версия 15:02, 12 июня 2012