7
правок
Изменения
Нет описания правки
'''Цифровая сортировка''' — один из алгоритмов сортировки, использующих внутреннюю структуру сортируемых объектов.
== Алгоритм ==
[[Файл:Цифровая_сортировка.png|thumb|right|450px|Пример цифровой сортировки трехзначных чисел, начиная с младших разрядов]][[Файл:Msd-sort.png|thumb|right|450px|Пример цифровой сортировки трехзначных чисел, начиная со старших разрядов]]
Имеем множество последовательностей одинаковой длины, состоящих из элементов, на которых задано [[Отношение порядка|отношение линейного порядка]]. Требуется отсортировать эти последовательности в лексикографическом порядке.
Для вышеперечисленных объектов наиболее часто в качестве устойчивой сортировки применяют [[сортировка подсчетом|сортировку подсчетом]].
Такой подход к алгоритму называют '''LSD-сортировкой''' (Least Significant Digit radix sort). Существует модификация алгоритма цифровой сортировки, анализирующая значения разрядов, начиная слева, с наиболее значащих разрядов. Данный алгоритм известен, как '''MSD-сортировка''' (Most Significant Digit radix sort).
=== Корректность алгоритма ===
Докажем, что данный алгоритм работает верно, используя метод математической индукции по номеру разряда. Пусть <tex> n </tex> {{---}} количество разрядов в сортируемых объектах.
== Псевдокод ==
=== LSD-сортировка ===
В качестве примера рассмотрим сортировку чисел. Как говорилось выше, в такой ситуации в качестве устойчивой сортировки применяют сортировку подсчетом, так как обычно количество различных значений разрядов не превосходит количества сортируемых элементов. Ниже приведен псевдокод цифровой сортировки, которой подается массив <tex> A </tex> <tex> m </tex>-разрядных чисел размера <tex> n </tex>. Сам по себе алгоритм представляет собой цикл по номеру разряда, на каждой итерации которого элементы массива <tex> A </tex> размещаются в нужном порядке во вспомогательном массиве <tex> B </tex>. Для подсчета количества объектов, <tex> i </tex>-й разряд которых одинаковый, а затем и для определения положения объектов в массиве <tex> B </tex> используется вспомогательный массив <tex> C </tex>. Функция <tex> digit(x, i) </tex> возвращает <tex> i </tex>-й разряд числа <tex> x </tex>. Также считаем, что значения разрядов меньше <tex> k </tex>.
radixSort(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] += 1; count = 0;
'''for''' j = 0 '''to''' k - 1
tmp = C[j]; C[j] = count; count = count + tmp;
'''for''' j = 0 '''to''' n - 1
d = digit(A[j], i); B[C[d]] = A[j]; C[d] += 1; A = B; === MSD-сортировка ===Сначала исходный массив делится на <tex>k</tex> частей, где <tex>k</tex> — основание, выбранное для представления сортируемых объектов. Эти части принято называть "корзинами" или "карманами". В первую корзину попадают элементы, у которых старший разряд с номером <tex>d = 0</tex> имеет значение <tex>0</tex>. Во вторую корзину попадают элементы, у которых старший разряд с номером <tex>d = 0</tex> имеет значение <tex>1</tex> и так далее. Затем элементы, попавшие в разные корзины, подвергаются рекурсивному разделению по следующему разряду с номером <tex>d = 1</tex>. Рекурсивный процесс разделения продолжается, пока не будут перебраны все разряды сортируемых объектов. В основу распределения элементов по корзинам положен метод распределяющего подсчета элементов с одинаковыми значениями в сортируемом разряде. Для этого выполняется просмотр массива и подсчет количества элементов с различными значениями в сортируемом разряде. Эти счетчики фиксируются во вспомогательном массиве счетчиков <tex>cnt</tex>. Затем счетчики используются для вычисления размеров корзин и определения границ разделения массива. В соответствии с этими границами сортируемые объекты переносятся во вспомогательный массив <tex>c</tex>, в котором размещены корзины.После того как корзины сформированы, содержимое вспомогательного массива <tex>c</tex> переносится обратно в исходный массив <tex>A</tex> и выполняется рекурсивное разделение новых частей по следующему разряду в пределах границ корзин, полученных на предыдущем шаге. <tex>m</tex> — максимальное количество разрядов в сортируемых объектах <tex>l</tex>, <tex>r</tex> — левая и правая границы части массива <tex>A</tex> radixSort(A, l, r, 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] = cnt[j + 1] + 1 '''for''' j = 2 '''to''' k cnt[j] = cnt[j] + cnt[j - 1] '''for''' i = l '''to''' r j = digit(A[i], d) c[l + cnt[j]] = A[i] cnt[j] = cnt[j] + 1 '''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)
==Сложность==
