Цифровая сортировка
Цифровая сортировка — один из алгоритмов сортировки, использующих внутреннюю структуру сортируемых объектов.
Алгоритм
Имеем множество последовательностей одинаковой длины, состоящих из элементов, на которых задано отношение линейного порядка. Требуется отсортировать эти последовательности в лексикографическом порядке.
По аналогии с разрядами чисел будем называть элементы, из которых состоят сортируемые объекты, разрядами. Сам алгоритм состоит в последовательной сортировке объектов какой-либо устойчивой сортировкой по каждому разряду, в порядке от младшего разряда к старшему, после чего последовательности будут расположены в требуемом порядке.
Примерами объектов, которые удобно разбивать на разряды и сортировать по ним, являются числа и строки.
- Для чисел уже существует понятие разряда, поэтому будем представлять числа как последовательности разрядов. Конечно, в разных системах счисления разряды одного и того же числа отличаются, поэтому перед сортировкой представим числа в удобной для нас системе счисления.
- Строки представляют из себя последовательности символов, поэтому в качестве разрядов в данном случае выступают отдельные символы, сравнение которых обычно происходит по соответствующим им кодам из таблицы кодировок. Для такого разбиения самый младший разряд — последний символ строки.
Для вышеперечисленных объектов наиболее часто в качестве устойчивой сортировки применяют сортировку подсчетом.
Такой подход к алгоритму называют LSD-сортировкой (Least Significant Digit radix sort). Существует модификация алгоритма цифровой сортировки, анализирующая значения разрядов, начиная слева, с наиболее значащих разрядов. Данный алгоритм известен, как MSD-сортировка (Most Significant Digit radix sort).
Корректность алгоритма LSD-сортировки
Докажем, что данный алгоритм работает верно, используя метод математической индукции по номеру разряда. Пусть — количество разрядов в сортируемых объектах.
База: . Очевидно, что алгоритм работает верно, потому что в таком случае мы просто сортируем младшие разряды какой-то заранее выбранной устойчивой сортировкой.
Переход: Пусть для алгоритм правильно отсортировал последовательности по младшим разрядам. Покажем, что в таком случае, при сортировке по -му разряду, последовательности также будут отсортированы в правильном порядке.
Вспомогательная сортировка разобьет все объекты на группы, в которых -й разряд объектов одинаковый. Рассмотрим такие группы. Для сортировки по отдельным разрядам мы используем устойчивую сортировку, следовательно порядок объектов с одинаковым -м разрядом не изменился. Но по предположению индукции по предыдущим разрядам последовательности были отсортированы правильно, и поэтому в каждой такой группе они будут отсортированы верно. Также верно, что сами группы находятся в правильном относительно друг друга порядке, а, следовательно, и все объекты отсортированы правильно по -м младшим разрядам.
Псевдокод
LSD-сортировка
В качестве примера рассмотрим сортировку чисел. Как говорилось выше, в такой ситуации в качестве устойчивой сортировки применяют сортировку подсчетом, так как обычно количество различных значений разрядов не превосходит количества сортируемых элементов. Ниже приведен псевдокод цифровой сортировки, которой подается массив размера -разрядных чисел . Сам по себе алгоритм представляет собой цикл по номеру разряда, на каждой итерации которого элементы массива размещаются в нужном порядке во вспомогательном массиве . Для подсчета количества объектов, -й разряд которых одинаковый, а затем и для определения положения объектов в массиве используется вспомогательный массив . Функция возвращает -й разряд числа . Также считаем, что значения разрядов меньше .
function radixSort(int[] A):
for i = 1 to m
for j = 0 to k - 1
C[j] = 0
for j = 0 to n - 1
d = digit(A[j], i)
C[d]++
count = 0
for j = 0 to k - 1
tmp = C[j]
C[j] = count
count += tmp
for j = 0 to n - 1
d = digit(A[j], i)
B[C[d]] = A[j]
C[d]++
A = B
MSD-сортировка
Будем считать, что у всех элементов одинаковое число разрядов. Если это не так, то положим на более старших разрядах элементы с самым маленьким значением — для чисел это . Сначала исходный массив делится на частей, где — основание, выбранное для представления сортируемых объектов. Эти части принято называть "корзинами" или "карманами". В первую корзину попадают элементы, у которых старший разряд с номером имеет значение . Во вторую корзину попадают элементы, у которых старший разряд с номером имеет значение и так далее. Затем элементы, попавшие в разные корзины, подвергаются рекурсивному разделению по следующему разряду с номером . Рекурсивный процесс разделения продолжается, пока не будут перебраны все разряды сортируемых объектов и пока размер корзины больше единицы. То есть останавливаемся когда или , где m — максимальное число разрядов в сортируемых объектах, , — левая и правая границы отрезка массива .
В основу распределения элементов по корзинам положен метод распределяющего подсчета элементов с одинаковыми значениями в сортируемом разряде. Для этого выполняется просмотр массива и подсчет количества элементов с различными значениями в сортируемом разряде. Эти счетчики фиксируются во вспомогательном массиве счетчиков . Затем счетчики используются для вычисления размеров корзин и определения границ разделения массива. В соответствии с этими границами сортируемые объекты переносятся во вспомогательный массив , в котором размещены корзины. После того как корзины сформированы, содержимое вспомогательного массива переносится обратно в исходный массив и выполняется рекурсивное разделение новых частей по следующему разряду в пределах границ корзин, полученных на предыдущем шаге.
Изначально запускаем функцию так
function radixSort(int[] A, int l, int r, int d):
if d > m or l >= r
return
for j = 0 to k + 1
cnt[j] = 0
for i = l to r
j = digit(A[i], d)
cnt[j + 1]++
for j = 2 to k
cnt[j] += cnt[j - 1]
for i = l to r
j = digit(A[i], d)
c[l + cnt[j]] = A[i]
cnt[j]++
for i = l to r
A[i] = c[i]
radixSort(A, l, l + cnt[0] - 1, d + 1)
for i = 1 to k
radixSort(A, l + cnt[i - 1], l + cnt[i] - 1, d + 1)
Сложность
Сложность LSD-сортировки
Пусть — количество разрядов, — количество объектов, которые нужно отсортировать, — время работы устойчивой сортировки. Цифровая сортировка выполняет итераций, на каждой из которой выполняется устойчивая сортировка и не более других операций. Следовательно время работы цифровой сортировки — .
Рассмотрим отдельно случай сортировки чисел. Пусть в качестве аргумента сортировке передается массив, в котором содержатся -значных чисел, и каждая цифра может принимать значения от до . Тогда цифровая сортировка позволяет отсортировать данный массив за время , если устойчивая сортировка имеет время работы . Если небольшое, то оптимально выбирать в качестве устойчивой сортировки сортировку подсчетом.
Если количество разрядов — константа, а , то сложность цифровой сортировки составляет , то есть она линейно зависит от количества сортируемых чисел.
Сложность MSD-сортировки
Пусть значения разрядов меньше , а количество разрядов — . При сортировке массива из одинаковых элементов MSD-сортировкой на каждом шаге все элементы будут находится в неубывающей по размеру корзине, а так как цикл идет по всем элементам массива, то получим, что время работы MSD-сортировки оценивается величиной , причем это время нельзя улучшить. Хорошим случаем для данной сортировки будет массив, при котором на каждом шаге каждая корзина будет делиться на частей. Как только размер корзины станет равен , сортировка перестанет рекурсивно запускаться в этой корзине. Таким образом, асимптотика будет . Это хорошо тем, что не зависит от числа разрядов.
Существует также модификация MSD-сортировки, при которой рекурсивный процесс останавливается при небольших размерах текущего кармана, и вызывается более быстрая сортировка, основанная на сравнениях (например, сортировка вставками).
См. также
Источники информации
- Википедия — Цифровая сортировка
- Визуализатор 1 — Java-аплет.
- Визуализатор 2 — Java-аплет.
- Дональд Кнут Искусство программирования, том 3. Сортировка и поиск
- Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ
