Сортировка подсчётом
Сортировка подсчётом — алгоритм сортировки целых чисел в диапазоне от до некоторой константы или сложных объектов, работающий за линейное время.
Сортировка целочисленных значение
Простой алгоритм
Это простейший вариант алгоритма. Создать вспомогательный массив , состоящий из нулей, затем последовательно прочитать элементы входного массива и для каждого увеличить на единицу. Теперь достаточно пройти по массиву и для каждого в массив последовательно записать число раз.
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;
Устойчивый алгоритм
Идея
Основная идея состоит в том, чтобы для каждого элемента входного массива подсчитать количество элементов, меньших данного. Эта информация будет указывать на позиции элементов в отсортированном массиве. Например, если для элемента количество таких элементов будет , то будет занимать -ю позицию в отсортированном массиве. Если элементы могут иметь одинаковые значения, то необходимо модифицировать алгоритм, так как нельзя разместить все такие элементы в одну позицию.
Реализация
В этом варианте помимо входного массива потребуется два вспомогательных массива — для счётчика и для отсортированного массива. Сначала следует заполнить массив нулями, и, пройдя по массиву , записать количество чисел равных в массив (строки 1 - 4). Далее подсчитывается число элементов меньше или равных текущему (строки 5 - 6). На последнем шаге алгоритма читается входной массив с конца, а в массив записываются элементы на те позиции, где они должны стоять; эта информация хранится в массиве (строки 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;
Обобщение на произвольный целочисленный диапазон
Если диапазон значений (минимимум и максимум) заранее не известен, можно найти их с помощью линейного поиска, что не повлияет на асимптотику алгоритма. При работе с массивом из необходимо вычитать минимум, а при обратной записи прибавлять.
Анализ
В первом алгоритме первые два цикла работают за и , соответственно; двойной цикл за . Во втором алгоритме циклы занимают , , и , соответственно. Итого оба алгоритма имеют линейную временную трудоёмкость . Используемая память в первом алгоритме равна , а во втором .
Использование сортировки подсчётом целесообразно, когда диапазон возможных значений входных данных достаточно мал по сравнению с количеством элементов в сортируемом множестве, например, если и все элементы натуральные числа меньшие , то время работы алгоритма равно . Эффективность алгоритма падает, когда необходимо сортировать различные элементы, попавшие в одну ячейку.
Сортировка сложных объектов
Постановка задачи
Иногда бывает очень желательно применить быстрый алгоритм сортировки подсчетом для упорядочивания набора каких-либо "сложных" данных. Под "сложными объектами" здесь подразумеваются структуры, содержащие в себе несколько полей. Одно из них мы выделим и назовем ключом, сортировка будет идти именно по нему (предполагается, что значения, принимаемые ключом — целые числа в диапазоне от до ).
Мы не сможем использовать здесь в точности тот же алгоритм, что и для сортировки подсчетом обычных целых чисел, потому что в наборе могут быть различные структуры, имеющие одинаковые ключи. Существует два способа справиться с этой проблемой — использовать списки для хранения структур в отсортированном массиве или заранее посчитать количество структур с одинаковыми ключами для каждого значения ключа.
Подсчет числа различных ключей
Описание
Исходная последовательность из структур хранится в массиве , а отсортированная — в массиве того же размера. Кроме того, используется вспомогательный массив с индексами от до .
Идея алгоритма состоит в предварительном подсчете количества элементов с различными ключами в исходном массиве и разделении результирующего массива на части соответствующей длины (будем называть их блоками). Затем при повторном проходе исходного массива каждый его элемент копируется в специально отведенный его ключу блок, в первую свободную ячейку. Это осуществляется с помощью массива индексов , в котором хранятся индексы начала блоков для различных ключей. — индекс в результирующем массиве, соответствующий первому элементу блока для ключа .
- Пройдем по исходному массиву и запишем в количество структур, ключ которых равен .
- Мысленно разобьем массив на блоков, длина каждого из которых равна соответственно , , ..., .
- Теперь массив нам больше не нужен. Превратим его в массив, хранящий в сумму элементов от до старого массива .
- Теперь "сдвинем" массив на элемент вперед: в новом массиве , а для , где — старый массив .
Это можно сделать за один проход по массиву , причем одновременно с предыдущим шагом.
После этого действия в массиве будут хранится индексы массива . указывает на начало блока в , соответствующего ключу .
- Произведем саму сортировку. Еще раз пройдем по исходному массиву и для всех будем помещать структуру в массив на место , а затем увеличивать на . Здесь — это ключ структуры, находящейся в массиве на -том месте.
Таким образом после завершения алгоритма в будет содержаться исходная последовательность в отсортированном виде (так как блоки расположены по возрастанию соответствующих ключей).
Стоит также отметить, что эта сортировка является устойчивой, так как два элемента с одинаковыми ключами будут добавлены в том же порядке, в каком просматривались в исходном массиве .
Псевдокод
Здесь и — массивы структур размера , с индексами от до . — целочисленный массив размера , с индексами от до , где — количество различных ключей.
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];
копируется структура целиком, а не только её ключ.
Анализ
Весь алгоритм состоит из двух проходов по массиву размера и одного прохода по массиву размера .
Его трудоемкость, таким образом, равна . На практике сортировку подсчетом имеет смысл применять, если , поэтому можно считать время работы алгоритма равным .
Как и в обычной сортировке подсчетом, требуется дополнительной памяти — на хранение массива размера и массива размера .
Источники
- Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. «Алгоритмы. Построение и анализ» — «Вильямс», 2011 г. — 1296 стр. — ISBN 978-5-8459-0857-5, 5-8459-0857-4, 0-07-013151-1
- Сортировка подсчетом — Википедия
- Wikipedia — Counting sort
