Сортировка подсчётом — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Реализация)
м (Дмитрий Мурзин переименовал страницу Сортировка подсчетом в Сортировка подсчётом: Ёфикация)
(не показано 30 промежуточных версий 4 участников)
Строка 1: Строка 1:
'''Сортировка подсчётом''' {{---}} алгоритм сортировки целых чисел в диапазоне от <tex>0</tex> до некоторой константы <tex>k</tex>, работающий за линейное время.
+
'''Сортировка подсчётом''' (англ. ''counting sort'') {{---}} алгоритм сортировки целых чисел в диапазоне от <tex>0</tex> до некоторой константы <tex>k</tex> или сложных объектов, работающий за линейное время.
 +
== Сортировка целых чисел ==
 +
Это простейший вариант алгоритма.
 +
=== Описание ===
 +
Исходная последовательность чисел длины <tex>n</tex>, а в конце отсортированная, хранится в массиве <tex>A</tex>. Также используется вспомогательный массив <tex>C</tex> с индексами от <tex>0</tex> до <tex>\mathrm k - 1</tex>, изначально заполняемый нулями.
  
== Простой алгоритм ==
+
* Последовательно пройдём по массиву <tex>A</tex> и запишем в <tex>C[i]</tex> количество чисел, равных <tex>i</tex>.
Это простейший вариант алгоритма. Создать вспомогательный массив <tex>C[0..k - 1]</tex>, состоящий из нулей, затем последовательно прочитать элементы входного массива <tex>A</tex> и для каждого <tex>A[i]</tex> увеличить <tex>C[A[i]]</tex> на единицу. Теперь достаточно пройти по массиву <tex>C</tex> и для каждого <tex>number \in \{0, ..., k - 1\}</tex> в массив <tex>A</tex> последовательно записать число <tex>number\</tex> <tex> C[number]</tex> раз.
+
 
 +
* Теперь достаточно пройти по массиву <tex>C</tex> и для каждого <tex>number \in \{0, ..., \mathrm k - 1\}</tex> в массив <tex>A</tex> последовательно записать число <tex>number\</tex> <tex> C[number]</tex> раз.
 +
 
 +
=== Псевдокод ===
 
<code>
 
<code>
  SimpleCountingSort
+
  '''function''' simpleCountingSort(A: '''int[n]'''):
     for number = 0 to k - 1
+
     '''for''' number = 0 '''to''' k - 1
         C[number] = 0;
+
         C[number] = 0  
     for i = 0 to length[A] - 1
+
     '''for''' i = 0 '''to''' n - 1
         C[A[i]] = C[A[i]] + 1;
+
         C[A[i]] = C[A[i]] + 1;    
 
     pos = 0;
 
     pos = 0;
     for number = 0 to k - 1
+
     '''for''' number = 0 '''to''' k - 1
         for i = 0 to C[j] - 1
+
         '''for''' i = 0 '''to''' C[number] - 1
 
             A[pos] = number;
 
             A[pos] = number;
 
             pos = pos + 1;
 
             pos = pos + 1;
 
</code>
 
</code>
  
== Устойчивый алгоритм ==
+
== Сортировка сложных объектов ==
 +
Сортировка целых чисел за линейное время это хорошо, но недостаточно. Иногда бывает очень желательно применить быстрый алгоритм [[#Сортировка целых чисел|сортировки подсчетом]] для упорядочивания набора каких-либо "сложных" данных. Под "сложными объектами" здесь подразумеваются структуры, содержащие в себе несколько полей. Одно из них мы выделим и назовем ключом, сортировка будет идти именно по нему (предполагается, что значения, принимаемые ключом {{---}} целые числа в диапазоне от <tex>0</tex> до <tex>\mathrm k-1</tex>).
 +
 
 +
Мы не сможем использовать здесь в точности тот же алгоритм, что и для сортировки подсчетом обычных целых чисел, потому что в наборе могут быть различные структуры, имеющие одинаковые ключи. Существует два способа справиться с этой проблемой {{---}} использовать списки для хранения структур в отсортированном массиве или заранее посчитать количество структур с одинаковыми ключами для каждого значения ключа. 
 +
 
 +
=== Описание ===
 +
Исходная последовательность из <tex>n</tex> структур хранится в массиве <tex>A</tex>, а отсортированная {{---}} в массиве <tex>B</tex> того же размера. Кроме того, используется вспомогательный массив <tex>P</tex> с индексами от <tex>0</tex> до <tex>\mathrm 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[0]</tex>, <tex>P[1]</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>x</tex> количество таких элементов будет <tex>42</tex>, то <tex>x</tex> будет занимать <tex>43</tex>-ю позицию в отсортированном массиве. Если элементы могут иметь одинаковые значения, то необходимо модифицировать алгоритм, так как нельзя разместить все такие элементы в одну позицию.
+
Таким образом после завершения алгоритма в <tex>B</tex> будет содержаться исходная последовательность в отсортированном виде (так как блоки расположены по возрастанию соответствующих ключей).
  
==== Реализация ====
+
Стоит также отметить, что эта сортировка является устойчивой, так как два элемента с одинаковыми ключами будут добавлены в том же порядке, в каком просматривались в исходном массиве <tex>A</tex>. Благодаря этому свойству существует [[цифровая сортировка]].
  
В этом варианте помимо входного массива <tex>A</tex> потребуется два вспомогательных массива — <tex>C[0..k - 1]</tex> для счётчика и <tex>B[0..n - 1]</tex> для отсортированного массива. Сначала следует заполнить массив <tex>C</tex> нулями, и, проходя по массиву <tex>A</tex>, записываем сколько у нас есть чисел равных <tex>A[i]</tex> в массив <tex>C</tex> (строки 1 - 4). Далее подсчитывается число элементов меньше или равных текущему (строки 5 - 6). На последнем шаге алгоритма читается входной массив с конца, а в массив <tex>B</tex> записываются элементы на те позиции, где они должны стоять; эта информация хранится в  массиве <tex>C</tex> (строки 7 - 9). Алгоритм устойчив. Устойчивость может потребоваться при [[Сортировка_подсчетом_сложных_объектов|сортировке сложных структур данных]].  
+
=== Псевдокод ===
 +
Здесь <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> {{---}} количество различных ключей.
 
<code>
 
<code>
  StableCountingSort
+
  '''function''' complexCountingSort(A: '''int[n]''', B: '''int[n]'''):
  for number = 0 to k - 1
+
    '''for''' i = 0 '''to''' k - 1
      C[number] = 0;
+
        P[i] = 0;        
  for i = 0 to length[A] - 1
+
    '''for''' i = 0 '''to''' length[A] - 1
        C[A[i]] = C[A[i]] + 1;
+
        P[A[i].key] = P[A[i].key] + 1;    
  for number = 1 to k - 1
+
    carry = 0;
      C[j] = C[j] + C[j - 1];
+
    '''for''' i = 0 '''to''' k - 1
  for i = length[A] - 1 to 0
+
        temporary = P[i];
      B[C[A[i]]] = A[i];
+
        P[i] = carry;
      C[A[i]] = C[A[i]] - 1;
+
        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;
 
</code>
 
</code>
 +
Здесь шаги 3 и 4 из описания объединены в один цикл.
 +
Обратите внимание, что в последнем цикле инструкцией
 +
B[P[A[i].key]] = A[i];
 +
копируется структура <tex>A[i]</tex> целиком, а не только её ключ.
 +
 +
== Анализ ==
 +
В первом алгоритме первые два цикла работают за <tex>\Theta(k)</tex> и <tex>\Theta(n)</tex>, соответственно; двойной цикл за <tex>\Theta(n + k)</tex>. Алгоритм имеет линейную временную трудоёмкость <tex>\Theta(n + k)</tex>. Используемая дополнительная память равна <tex>\Theta(k)</tex>.
  
== Обобщение на произвольный целочисленный диапазон ==
+
Второй алгоритм состоит из двух проходов по массиву <tex>A</tex> размера <tex>n</tex> и одного прохода по массиву <tex>P</tex> размера <tex>k</tex>.
Если диапазон значений (минимимум и максимум) заранее не известен, можно найти их с помощью линейного поиска, что не повлияет на асимптотику алгоритма. При работе с массивом <tex>C</tex> из <tex>A[i]</tex> необходимо вычитать минимум, а при обратной записи прибавлять.
+
Его трудоемкость, таким образом, равна <tex>\Theta(n + k)</tex>. На практике сортировку подсчетом имеет смысл применять, если <tex>k = O(n)</tex>, поэтому можно считать время работы алгоритма равным <tex>\Theta(n)</tex>. <br>
 +
Как и в обычной сортировке подсчетом, требуется <tex>\Theta(n + k)</tex> дополнительной памяти {{---}} на хранение массива <tex>B</tex> размера <tex>n</tex> и массива <tex>P</tex> размера <tex>k</tex>.
  
== Анализ ==
+
Алгоритм работает за линейное время, но является псевдополиномиальным.
В первом алгоритме первые два цикла работают за <tex>\Theta(k)</tex> и <tex>\Theta(n)</tex>, соответственно; двойной цикл за <tex>\Theta(n + k)</tex>. Во втором алгоритме циклы занимают <tex>\Theta(k)</tex>, <tex>\Theta(n)</tex>, <tex>\Theta(k)</tex> и <tex>\Theta(n)</tex>, соответственно. Итого оба алгоритма имеют линейную временную трудоёмкость <tex>\Theta(n + k)</tex>. Используемая память в первом алгоритме равна <tex>\Theta(k)</tex>, а во втором <tex>\Theta(n + k)</tex>.
 
  
Использование сортировки подсчётом целесообразно, когда диапазон возможных значений входных данных достаточно мал по сравнению с количеством элементов в сортируемом множестве, например, если <tex>n = 1000000</tex> и все элементы натуральные числа меньшие <tex>1000</tex>, то время работы алгоритма равно <tex>\Theta(n)</tex>. Эффективность алгоритма падает, когда необходимо сортировать различные элементы, попавшие в одну ячейку.
+
== Поиск диапазона ключей ==
 +
Если диапазон значений не известен заранее, то его можно найти с помощью линейного поиска минимума и максимума в исходном массиве, что не повлияет на асимптотику алгоритма. <br>
 +
Нужно учитывать, что минимум может быть отрицательным, в то время как в массиве <tex>P</tex> индексы от <tex>0</tex> до <tex>k-1</tex>. Поэтому при работе с массивом <tex>P</tex> из исходного <tex>A[i]</tex>  необходимо вычитать минимум, а при обратной записи в <tex>B[i]</tex> прибавлять его.
  
== Источники ==
+
== Источники информации ==
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. «Алгоритмы. Построение и анализ» {{---}} «Вильямс», 2011 г. {{---}} 1296 стр. {{---}} ISBN 978-5-8459-0857-5, 5-8459-0857-4, 0-07-013151-1
 
 
* [http://ru.wikipedia.org/wiki/Сортировка_подсчётом Сортировка подсчетом {{---}} Википедия]
 
* [http://ru.wikipedia.org/wiki/Сортировка_подсчётом Сортировка подсчетом {{---}} Википедия]
 +
* [http://en.wikipedia.org/wiki/Counting_sort Counting sort {{---}} Wikipedia]
 +
* Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 224{{---}}226.
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Сортировки]]
 
[[Категория: Сортировки]]
 +
[[Категория: Другие сортировки]]

Версия 23:50, 31 января 2019

Сортировка подсчётом (англ. counting sort) — алгоритм сортировки целых чисел в диапазоне от [math]0[/math] до некоторой константы [math]k[/math] или сложных объектов, работающий за линейное время.

Сортировка целых чисел

Это простейший вариант алгоритма.

Описание

Исходная последовательность чисел длины [math]n[/math], а в конце отсортированная, хранится в массиве [math]A[/math]. Также используется вспомогательный массив [math]C[/math] с индексами от [math]0[/math] до [math]\mathrm k - 1[/math], изначально заполняемый нулями.

  • Последовательно пройдём по массиву [math]A[/math] и запишем в [math]C[i][/math] количество чисел, равных [math]i[/math].
  • Теперь достаточно пройти по массиву [math]C[/math] и для каждого [math]number \in \{0, ..., \mathrm k - 1\}[/math] в массив [math]A[/math] последовательно записать число [math]number\[/math] [math] C[number][/math] раз.

Псевдокод

function simpleCountingSort(A: int[n]): 
    for number = 0 to k - 1
        C[number] = 0 
    for i = 0 to n - 1
        C[A[i]] = C[A[i]] + 1;     
    pos = 0;
    for number = 0 to k - 1
        for i = 0 to C[number] - 1
            A[pos] = number;
            pos = pos + 1;

Сортировка сложных объектов

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

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

Описание

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

Идея алгоритма состоит в предварительном подсчете количества элементов с различными ключами в исходном массиве и разделении результирующего массива на части соответствующей длины (будем называть их блоками). Затем при повторном проходе исходного массива каждый его элемент копируется в специально отведенный его ключу блок, в первую свободную ячейку. Это осуществляется с помощью массива индексов [math]P[/math], в котором хранятся индексы начала блоков для различных ключей. [math]P[key][/math] — индекс в результирующем массиве, соответствующий первому элементу блока для ключа [math]key[/math].

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

Building P.png

  • Мысленно разобьем массив [math]B[/math] на [math]k[/math] блоков, длина каждого из которых равна соответственно [math]P[0][/math], [math]P[1][/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]0[/math] до [math]k-1[/math], где [math]k[/math] — количество различных ключей.

function complexCountingSort(A: int[n], B: int[n]):
    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];

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

Анализ

В первом алгоритме первые два цикла работают за [math]\Theta(k)[/math] и [math]\Theta(n)[/math], соответственно; двойной цикл за [math]\Theta(n + k)[/math]. Алгоритм имеет линейную временную трудоёмкость [math]\Theta(n + k)[/math]. Используемая дополнительная память равна [math]\Theta(k)[/math].

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

Алгоритм работает за линейное время, но является псевдополиномиальным.

Поиск диапазона ключей

Если диапазон значений не известен заранее, то его можно найти с помощью линейного поиска минимума и максимума в исходном массиве, что не повлияет на асимптотику алгоритма.
Нужно учитывать, что минимум может быть отрицательным, в то время как в массиве [math]P[/math] индексы от [math]0[/math] до [math]k-1[/math]. Поэтому при работе с массивом [math]P[/math] из исходного [math]A[i][/math] необходимо вычитать минимум, а при обратной записи в [math]B[i][/math] прибавлять его.

Источники информации