Сортировка подсчётом

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

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

Простой алгоритм

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

SimpleCountingSort
    for number = 0 to k - 1
        C[number] = 0;
    for i = 0 to length[A] - 1
        C[A[i]] = C[A[i]] + 1;
    pos = 0;
    for number = 0 to k - 1
        for i = 0 to C[j] - 1
            A[pos] = number;
            pos = pos + 1;

Устойчивый алгоритм

Идея

Основная идея состоит в том, чтобы для каждого элемента входного массива подсчитать количество элементов, меньших данного. Эта информация будет указывать на позиции элементов в отсортированном массиве. Например, если для элемента [math]x[/math] количество таких элементов будет [math]42[/math], то [math]x[/math] будет занимать [math]43[/math]-ю позицию в отсортированном массиве. Если элементы могут иметь одинаковые значения, то необходимо модифицировать алгоритм, так как нельзя разместить все такие элементы в одну позицию.

Реализация

В этом варианте помимо входного массива [math]A[/math] потребуется два вспомогательных массива — [math]C[0..k - 1][/math] для счётчика и [math]B[0..n - 1][/math] для отсортированного массива. Сначала следует заполнить массив [math]C[/math] нулями, и, пройдя по массиву [math]A[/math], записать количество чисел равных [math]A[i][/math] в массив [math]C[/math] (строки 1 - 4). Далее подсчитывается число элементов меньше или равных текущему (строки 5 - 6). На последнем шаге алгоритма читается входной массив с конца, а в массив [math]B[/math] записываются элементы на те позиции, где они должны стоять; эта информация хранится в массиве [math]C[/math] (строки 7 - 9). Алгоритм устойчив. Устойчивость может потребоваться при сортировке сложных структур данных.

StableCountingSort
  for number = 0 to k - 1
      C[number] = 0;
  for i = 0 to length[A] - 1
       C[A[i]] = C[A[i]] + 1;
  for number = 1 to k - 1
      C[j] = C[j] + C[j - 1];
  for i = length[A] - 1 to 0
      B[C[A[i]]] = A[i];
      C[A[i]] = C[A[i]] - 1;

Обобщение на произвольный целочисленный диапазон

Если диапазон значений (минимимум и максимум) заранее не известен, можно найти их с помощью линейного поиска, что не повлияет на асимптотику алгоритма. При работе с массивом [math]C[/math] из [math]A[i][/math] необходимо вычитать минимум, а при обратной записи прибавлять.

Анализ

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

Использование сортировки подсчётом целесообразно, когда диапазон возможных значений входных данных достаточно мал по сравнению с количеством элементов в сортируемом множестве, например, если [math]n = 1000000[/math] и все элементы натуральные числа меньшие [math]1000[/math], то время работы алгоритма равно [math]\Theta(n)[/math]. Эффективность алгоритма падает, когда необходимо сортировать различные элементы, попавшие в одну ячейку.

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

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

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

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

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

Описание

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

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

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

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

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

• Теперь "сдвинем" массив [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].

• Произведем саму сортировку. Еще раз пройдем по исходному массиву [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]-том месте.

Таким образом после завершения алгоритма в [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] — количество различных ключей.

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];

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

Анализ

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

Источники

• Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. «Алгоритмы. Построение и анализ» — «Вильямс», 2011 г. — 1296 стр. — ISBN 978-5-8459-0857-5, 5-8459-0857-4, 0-07-013151-1
• Сортировка подсчетом — Википедия
• Wikipedia — Counting sort