Изменения

[[Файл:Radix.gif|thumb|right|590px|Пример цифровой сортировки]]'''Цифровая сортировка''' — (англ. ''radix sort'') {{---}} один из алгоритмов сортировки, использующих внутреннюю структуру сортируемых объектов.

При [[Файл:Цифровая_сортировка.png|thumb|right|450px|Пример цифровой сортировке данные разбиваются сортировки трехзначных чисел, начиная с младших разрядов]][[Файл:Msd-sort.png|thumb|right|450px|Пример цифровой сортировки трехзначных чисел, начиная со старших разрядов]]Имеем множество последовательностей одинаковой длины, состоящих из элементов, на "разряды"которых задано [[Отношение порядка|отношение линейного порядка]]. Требуется отсортировать эти последовательности в лексикографическом порядке. По аналогии с разрядами чисел будем называть элементы, из которых состоят сортируемые объекты, после чего они сортируются разрядами. Сам алгоритм состоит в последовательной сортировке объектов какой-либо устойчивой сортировкой по каждому разряду, в порядке от младшего разряда к старшему, после чего последовательности будут расположены в требуемом порядке. Примерами объектов, которые удобно разбивать на разряды и сортировать по ним, являются числа и строки. *Для чисел уже существует понятие разряда, поэтому будем представлять числа как последовательности разрядов. Конечно, в разных системах счисления разряды одного и того же числа отличаются, поэтому перед сортировкой представим числа в удобной для нас системе счисления. *Строки представляют из себя последовательности символов, поэтому в качестве разрядов в данном случае выступают отдельные символы, сравнение которых обычно происходит по соответствующим им кодам из [[Представление символов, таблицы кодировок#Таблицы кодировок|таблицы кодировок]]. Для такого разбиения самый младший разряд {{---}} последний символ строки. Для вышеперечисленных объектов наиболее часто в качестве устойчивой сортировки применяют [[сортировка подсчетом|сортировку подсчетом]]. Такой подход к алгоритму называют '''LSD-сортировкой''' (Least Significant Digit radix sort). Существует модификация алгоритма цифровой сортировки, анализирующая значения разрядов, начиная слева, с наиболее значащих разрядов. Данный алгоритм известен, как '''MSD-сортировка''' (Most Significant Digit radix sort).=== Корректность алгоритма LSD-сортировки ===Докажем, что данный алгоритм работает верно, используя метод математической индукции по номеру разряда. Для простоты рассуждений будем предполагать, что объекты сортируются по неубыванию. Пусть <tex> n </tex> {{---}} количество разрядов в сортируемых объектах.*<b> База</b>: <tex> n = 1 </tex>. Очевидно, что алгоритм работает верно, потому что в таком случае мы просто сортируем младшие разряды какой-то заранее выбранной стабильной устойчивой сортировкой.*<b> Переход</b>: Пусть для <tex> n = k </tex> алгоритм правильно отсортировал элементы последовательности по <tex> k </tex> младшим разрядам. Покажем, что в таком случае, при сортировке по <tex> (k + 1) </tex>-ому му разряду, объекты последовательности также будут отсортированы в правильном порядке.  Вспомогательная сортировка разобьет все объекты на группы, в которых <tex> (k + 1) </tex>-ый й разряд объектов одинаковый. Рассмотрим такие группы. Для сортировки по отдельным разрядам мы используем стабильную устойчивую сортировку, следовательно порядок объектов с одинаковым <tex> (k + 1) </tex>-ым м разрядом не изменился. Но по предположению индукции по предыдущим <tex> k </tex> разрядам объекты последовательности были отсортированы правильно, и поэтому в каждой такой группе объекты они будут отсортированы верно. Также верно, что сами группы находятся в правильном относительно друг друга порядке, а , следовательно , и все элементы объекты отсортированы правильно по <tex> (k + 1) </tex>-ым м младшим разрядам.  

=== LSD-сортировка ===В качестве примера рассмотрим сортировку чисел. Как говорилось выше, в такой ситуации в качестве стабильной устойчивой сортировки применяют сортировку подсчетом, так как обычно количество различных значений разрядов не превосходит количества сортируемых элементов. Ниже приведен псевдокод цифровой сортировки, которой подается массив <tex> A </tex> размера <tex> n </tex> <tex> m </tex>-разрядных чисел размера . Сам по себе алгоритм представляет собой цикл по номеру разряда, на каждой итерации которого элементы массива <tex> A </tex> размещаются в нужном порядке во вспомогательном массиве <tex> B </tex>. Для подсчета количества объектов, <tex> i </tex>-й разряд которых одинаковый, а затем и для определения положения объектов в массиве <tex> B </tex> используется вспомогательный массив <tex> n C </tex>. Функция <tex> \mathrm{digit(x, i) } </tex> возвращает <tex> i </tex>-ый й разряд числа <tex> x </tex>. Так же Также считаем, что значения разрядов меньше <tex> k </tex>. '''function''' radixSort(int[] A): '''for ''' i = 1 '''to ''' m '''for ''' j = 0 '''to ''' k - 1 // обнуление вспомогательного массива С, C[j] = 0; // использующегося в качестве счетчика '''for ''' j = 0 '''to ''' n - 1 C[d = digit(A[j], i)] = C[digit(A[j], i)d] + 1; + count = 0 '''for ''' j = 1 0 '''to ''' k - 1 tmp = C[j] = C[j] = count count + C[j - 1];= tmp '''for ''' j = 0 '''to''' n - 1 to 0 // заполняем вспомогательный массив B, в котором после каждой итерации B[C[d = digit(A[j], i) B[C[d]] = A[j]; C[d]++ A = B === MSD-сортировка ===Будем считать, что у всех элементов одинаковое число разрядов. Если это не так, то положим на более старших разрядах элементы с самым маленьким значением — для чисел это <tex>0</tex>. Сначала исходный массив делится на <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>d > m</tex> или <tex>l \geqslant r</tex>, где m — максимальное число разрядов в сортируемых объектах, <tex>l</tex>, <tex>r</tex> — левая и правая границы отрезка массива <tex>A</tex>. В основу распределения элементов по корзинам положен метод распределяющего подсчета элементов с одинаковыми значениями в сортируемом разряде. Для этого выполняется просмотр массива и подсчет количества элементов с различными значениями в сортируемом разряде. Эти счетчики фиксируются во вспомогательном массиве счетчиков <tex>cnt</tex>. Затем счетчики используются для вычисления размеров корзин и определения границ разделения массива. В соответствии с этими границами сортируемые объекты переносятся во вспомогательный массив <tex>c</tex>, в котором размещены корзины.После того как корзины сформированы, содержимое вспомогательного массива <tex>c</tex> переносится обратно в исходный массив <tex>A</ внешнего цикла числа отсортированы tex> и выполняется рекурсивное разделение новых частей по младшим следующему разряду в пределах границ корзин, полученных на предыдущем шаге. Изначально запускаем функцию так <math>\mathrm{radixSort(A, 0, A.length - 1, 1)}</math>  '''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 C[ j = digit(A[ji], id) cnt[j + 1] ++ '''for''' j = C2 '''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, i)l, l + cnt[0] - 1;, d + 1) '''for''' i = 1 '''to''' k radixSort(A = B;, l + cnt[i - 1], l + cnt[i] - 1, d + 1)

===Сложность LSD-сортировки===Пусть <tex> m </tex> {{---}} количество разрядов, <tex> n </tex> {{---}} количество объектов, которые нужно отсортировать, <tex> T(n) </tex> {{---}} время работы устойчивой сортировки. Цифровая сортировка выполняет <tex> k </tex> итераций, на каждой из которой выполняется устойчивая сортировка и не более <tex> O(1) </tex> других операций. Следовательно время работы цифровой сортировки {{---}} <tex> O(k \cdot T(n)) </tex>.

Рассмотрим отдельно случай сортировки чисел. Пусть в качестве аргумента сортировке передается массив, в котором содержатся <tex> n </tex> <tex> m </tex>-значных чисел, и каждая цифра может принимать значения от <tex> 0 </tex> до <tex> k - 1 </tex>. Тогда цифровая сортировка позволяет отсортировать данный массив за время <tex> \ThetaO(m \cdot (n + k)) </tex>, если устойчивая сортировка имеет время работы <tex> \ThetaO(n + k) </tex>. Если <tex> k </tex> небольшое, то оптимально выбирать в качестве устойчивой сортировки сортировку подсчетом.

Если количество разрядов {{---}} константа, а <tex> k =O(n) </tex>, то сложность цифровой сортировки составляет <tex> O(n) </tex>, то есть она линейно зависит от количества сортируемых чисел.= Литература ==Сложность MSD-сортировки===Пусть значения разрядов меньше <tex>b</tex>, а количество разрядов {{---}} <tex>k</tex>. При сортировке массива из одинаковых элементов MSD-сортировкой на каждом шаге все элементы будут находится в неубывающей по размеру корзине, а так как цикл идет по всем элементам массива, то получим, что время работы MSD-сортировки оценивается величиной <tex>O(nk)</tex>, причем это время нельзя улучшить. Хорошим случаем для данной сортировки будет массив, при котором на каждом шаге каждая корзина будет делиться на <tex>b</tex> частей. Как только размер корзины станет равен <tex>1</tex>, сортировка перестанет рекурсивно запускаться в этой корзине. Таким образом, асимптотика будет <math>\Omega(n\log_b{n})</math>. Это хорошо тем, что не зависит от числа разрядов. Существует также модификация MSD-сортировки, при которой рекурсивный процесс останавливается при небольших размерах текущего кармана, и вызывается более быстрая сортировка, основанная на сравнениях (например, сортировка вставками). == См. также ==* [[Сортировка подсчетом]]* [[Сортировка вставками]] == Источники информации ==* [[wikipedia:ru:Поразрядная сортировка|Википедия {{---}} Цифровая сортировка]]* [http://rain.ifmo.ru/cat/view.php/vis/sorts/linear-2005 Визуализатор 1] — Java-аплет.* [http://rain.ifmo.ru/cat/view.php/vis/sorts/linear-2001 Визуализатор 2] — Java-аплет.