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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Устойчивый алгоритм)
м (rollbackEdits.php mass rollback)
 
(не показано 45 промежуточных версий 8 участников)
Строка 1: Строка 1:
'''Сортировка подсчётом''' алгоритм сортировки, в котором используется диапазон чисел сортируемого массива или списка для подсчёта совпадающих элементов. Применение сортировки подсчётом целесообразно лишь тогда, когда сортируемые числа имеют (или их можно отобразить в) диапазон возможных значений, который достаточно мал по сравнению с сортируемым множеством, например, миллион натуральных чисел меньших 1000. Эффективность алгоритма падает, если при попадании нескольких различных элементов в одну ячейку, их надо дополнительно сортировать.  
+
'''Сортировка подсчётом''' (англ. ''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>j \in \{0, ..., k - 1\}</tex> в массив <tex>A</tex> последовательно записать число <tex>j</tex> <tex> C[j]</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 i = 0 to k - 1
+
     '''for''' number = 0 '''to''' k - 1
         C[i] = 0;
+
         C[number] = 0  
     for i = 0 to n - 1
+
     '''for''' i = 0 '''to''' n - 1
         C[A[i]] = C[A[i]] + 1;
+
         C[A[i]] = C[A[i]] + 1;    
     b = 0;
+
     pos = 0;
     for j = 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[b] = j;
+
             A[pos] = number;
             b = b + 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>C[0..k - 1]</tex> для счётчика и <tex>B[0..n - 1]</tex> для отсортированного массива. Сначала следует заполнить массив <tex>C</tex> нулями, и для каждого <tex>A[i]</tex> увеличить <tex>C[A[i]]</tex> на 1. Далее подсчитывается число элементов меньше или равных текущему. Для этого каждый <tex>C[j]</tex>, начиная с <tex>C[1]</tex>, увеличивают на <tex>C[j - 1]</tex>. На последнем шаге алгоритма читается входной массив с конца, значение <tex>C[A[i]]</tex> уменьшается на 1 и в каждый <tex>B[C[A[i]]]</tex> записывается <tex>A[i]</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>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> {{---}} количество различных ключей.
 
<code>
 
<code>
  StableCountingSort
+
  '''function''' complexCountingSort(A: '''int[n]''', B: '''int[n]'''):
     for i = 0 to k - 1
+
     '''for''' i = 0 '''to''' k - 1
         C[i] = 0;
+
         P[i] = 0;        
     for i = 0 to n - 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 j = 1 to k - 1
+
     carry = 0;
         C[j] = C[j] + C[j - 1];
+
    '''for''' i = 0 '''to''' k - 1
     for i = n - 1 to 0
+
         temporary = P[i];
         C[A[i]] = C[A[i]] - 1;
+
        P[i] = carry;
         B[C[A[i]]] = A[i];
+
        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>.
  
Если диапазон значений (min и max) заранее не известен, можно воспользоваться линейным поиском min и max, что не повлияет на асимптотику алгоритма. При работе с массивом <tex>C</tex> из <tex>A[i]</tex> необходимо вычитать min, а при обратной записи прибавлять.  
+
Второй алгоритм состоит из двух проходов по массиву <tex>A</tex> размера <tex>n</tex> и одного прохода по массиву <tex>P</tex> размера <tex>k</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>.
+
Алгоритм работает за линейное время, но является псевдополиномиальным.
  
 +
== Поиск диапазона ключей ==
 +
Если диапазон значений не известен заранее, то его можно найти с помощью линейного поиска минимума и максимума в исходном массиве, что не повлияет на асимптотику алгоритма. <br>
 +
Нужно учитывать, что минимум может быть отрицательным, в то время как в массиве <tex>P</tex> индексы от <tex>0</tex> до <tex>k-1</tex>. Поэтому при работе с массивом <tex>P</tex> из исходного <tex>A[i]</tex>  необходимо вычитать минимум, а при обратной записи в <tex>B[i]</tex> прибавлять его.
  
== Ссылки ==
+
== Источники информации ==
 +
* [http://ru.wikipedia.org/wiki/Сортировка_подсчётом Сортировка подсчетом {{---}} Википедия]
 +
* [http://en.wikipedia.org/wiki/Counting_sort Counting sort {{---}} Wikipedia]
 +
* Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 224{{---}}226.
  
[http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%BF%D0%BE%D0%B4%D1%81%D1%87%D1%91%D1%82%D0%BE%D0%BC Википедия: Сортировка подсчетом]
+
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Сортировки]]
 +
[[Категория: Другие сортировки]]

Текущая версия на 19:33, 4 сентября 2022

Сортировка подсчётом (англ. 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] прибавлять его.

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