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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Добавлены иллюстрации-примеры)
(Новое разбиение на разделы, псевдокод, анализ)
Строка 1: Строка 1:
 
{{В разработке}}
 
{{В разработке}}
  
 +
== Постановка задачи ==
 
Иногда бывает очень желательно применить быстрый алгоритм [[Сортировка подсчетом|сортировки подсчетом]] для упорядочивания набора каких-либо "сложных" данных. Под "сложными объектами" здесь подразумеваются структуры, содержащие в себе несколько полей. Одно из них мы выделим и назовем ключом, сортировка будет идти именно по нему (предполагается, что значения, принимаемые ключом - целые числа в диапазоне от <tex>0</tex> до <tex>k-1</tex>).
 
Иногда бывает очень желательно применить быстрый алгоритм [[Сортировка подсчетом|сортировки подсчетом]] для упорядочивания набора каких-либо "сложных" данных. Под "сложными объектами" здесь подразумеваются структуры, содержащие в себе несколько полей. Одно из них мы выделим и назовем ключом, сортировка будет идти именно по нему (предполагается, что значения, принимаемые ключом - целые числа в диапазоне от <tex>0</tex> до <tex>k-1</tex>).
  
Строка 16: Строка 17:
  
 
== Подсчет числа различных ключей ==
 
== Подсчет числа различных ключей ==
 +
=== Описание ===
 
Здесь исходная последовательность из <tex>n</tex> структур хранится в массиве <tex>A</tex>, а отсортированная - в массиве <tex>B</tex> того же размера. Кроме того используется вспомогательный массив <tex>P</tex> с индексами от <tex>0</tex> до <tex>k-1</tex>.
 
Здесь исходная последовательность из <tex>n</tex> структур хранится в массиве <tex>A</tex>, а отсортированная - в массиве <tex>B</tex> того же размера. Кроме того используется вспомогательный массив <tex>P</tex> с индексами от <tex>0</tex> до <tex>k-1</tex>.
  
Строка 37: Строка 39:
 
Стоит также отметить, что эта сортировка является устойчивой, так как два элемента с одинаковыми ключами будут добавлены в том же порядке, в каком просматривались в исходном массиве <tex>A</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>k</tex> - количество различных ключей), с индексами от <tex>0</tex> до <tex>k-1</tex>. <tex>i</tex>, <tex>carry</tex>, <tex>temporary</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 + P[i];
 +
   
 +
    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</tex> значительно меньше <tex>n</tex>, поэтому можно считать время работы алгоритма равным <tex> O(n)</tex>.
 +
Как и в обычной сортировке подсчетом, алгоритму требуется <tex> O(n + k)</tex> дополнительной памяти.
 +
 
 +
== Источники ==
 
* [http://ru.wikipedia.org/wiki/Сортировка_подсчётом Википедия {{---}} Сортировка подсчетом]
 
* [http://ru.wikipedia.org/wiki/Сортировка_подсчётом Википедия {{---}} Сортировка подсчетом]
 
* [http://en.wikipedia.org/wiki/Counting_sort Wikipedia {{---}} Counting sort]
 
* [http://en.wikipedia.org/wiki/Counting_sort Wikipedia {{---}} Counting sort]

Версия 15:08, 17 мая 2012

Эта статья находится в разработке!

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

Иногда бывает очень желательно применить быстрый алгоритм сортировки подсчетом для упорядочивания набора каких-либо "сложных" данных. Под "сложными объектами" здесь подразумеваются структуры, содержащие в себе несколько полей. Одно из них мы выделим и назовем ключом, сортировка будет идти именно по нему (предполагается, что значения, принимаемые ключом - целые числа в диапазоне от [math]0[/math] до [math]k-1[/math]).

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

Использование списков

Пусть далее исходная последовательность из [math]n[/math] структур хранится в массиве [math]A[/math], а отсортированная - в массиве [math]P[/math] с индексами от [math]0[/math] до [math]k-1[/math].

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

List solution.png

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

Подсчет числа различных ключей

Описание

Здесь исходная последовательность из [math]n[/math] структур хранится в массиве [math]A[/math], а отсортированная - в массиве [math]B[/math] того же размера. Кроме того используется вспомогательный массив [math]P[/math] с индексами от [math]0[/math] до [math]k-1[/math].

  • Пройдем по исходному массиву [math]A[/math] и запишем в [math]P[i][/math] количество структур, ключ которых равен [math]i[/math].

Building P.png

  • Мысленно разобьем массив [math]B[/math] на [math]k[/math] блоков, длина каждого из которых равна соответственно [math]P[1][/math], [math]P[2][/math], ..., [math]P[k][/math].

Splitting B w colors.png

  • Теперь массив [math]P[/math] нам больше не нужен. Превратим его в массив, хранящий в [math]P[i][/math] сумму элементов от [math]0[/math] до [math]i-1[/math] старого массива [math]P[/math].

P after adding.png

  • Теперь "сдвинем" массив [math]P[/math] на элемент вперед: в новом массиве [math]P[0] = 0[/math], а для [math]i \gt 0[/math] [math]P[i] = P_{old}[i-1][/math], где [math]P_{old}[/math] - старый массив [math]P[/math].
    Это можно сделать за один проход по массиву [math]P[/math], причем одновременно с предыдущим шагом.
    После этого действия в массиве [math]P[/math] будут хранится индексы массива [math]B[/math]. [math]P[key][/math] указывает на начало блока в [math]B[/math], соответствующего ключу [math]key[/math].

P as array of pointers.png

  • Произведем саму сортировку. Еще раз пройдем по исходному массиву [math]A[/math] и для всех [math]i \in [0, n-1][/math] будем помещать структуру [math]A[i][/math] в массив [math]B[/math] на место [math]P[A[i].key][/math], а затем увеличивать [math]P[A[i].key][/math] на [math]1[/math]. Здесь [math]A[i].key[/math] — это ключ структуры, находящейся в массиве [math]A[/math] на [math]i[/math]-том месте.

Sorting A.png

Таким образом после завершения алгоритма в [math]B[/math] будет содержаться исходная последовательность в отсортированном виде (так как блоки расположены по возрастанию соответствующих ключей).

Стоит также отметить, что эта сортировка является устойчивой, так как два элемента с одинаковыми ключами будут добавлены в том же порядке, в каком просматривались в исходном массиве [math]A[/math].

Псевдокод

Здесь [math]A[/math] и [math]B[/math] — массивы структур размера [math]n[/math], с индексами от [math]0[/math] до [math]n-1[/math]. [math]P[/math] — целочисленный массив размера [math]k[/math] ([math]k[/math] - количество различных ключей), с индексами от [math]0[/math] до [math]k-1[/math]. [math]i[/math], [math]carry[/math], [math]temporary[/math] — целочисленные переменные.

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 + P[i];
    
    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];

копируется структура [math]A[i][/math] целиком, а не только её ключ.

Анализ

Весь алгоритм состоит из двух проходов по массиву [math]A[/math] размера [math]n[/math] и одного прохода по массиву [math]P[/math], размера [math]k[/math]. Его трудоемкость, таким образом, равна [math] O(n + k)[/math]. На практике сортировку подсчетом имеет смысл применять, если [math]k[/math] значительно меньше [math]n[/math], поэтому можно считать время работы алгоритма равным [math] O(n)[/math]. Как и в обычной сортировке подсчетом, алгоритму требуется [math] O(n + k)[/math] дополнительной памяти.

Источники