1632
правки
Изменения
м
Сложность Существует также модификация MSD-сортировки оценивается величиной <tex>O, при которой рекурсивный процесс останавливается при небольших размерах текущего кармана, и вызывается более быстрая сортировка, основанная на сравнениях (n \log_k nнапример, сортировка вставками)</tex>. При больших k величина <tex>\log_k n</tex> становится малой и сложность становится линейной функцией <tex>O(n)</tex>
Существует так же модификация MSD-сортировки, при которой рекурсивный процесс останавливается при небольших размерах текущего кармана и вызывается более быстрая сортировка основанная на сравнениях (например, сортировка == См. также ==* [[Сортировка подсчетом]]* [[Сортировка вставками). ]]
Таким образом, если k небольшое, то лучше использовать LSD-сортировку, при больших k {{---}} MSD-сортировку.
* [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-аплет.
== Смотри также ==
* [[Сортировка подсчетом]]
* [[Сортировка вставками]]
* [[wikipedia:ru:Поразрядная сортировка|Википедия {{---}} Цифровая сортировка]]
rollbackEdits.php mass rollback
'''Цифровая сортировка''' — (англ. ''radix sort'') {{---}} один из алгоритмов сортировки, использующих внутреннюю структуру сортируемых объектов.
== Алгоритм ==
[[Файл:Цифровая_сортировка.png|thumb|right|450px|Пример цифровой сортировки трехзначных чисел, начиная с младших разрядов]]
== Псевдокод ==
=== LSD-сортировка ===
В качестве примера рассмотрим сортировку чисел. Как говорилось выше, в такой ситуации в качестве устойчивой сортировки применяют сортировку подсчетом, так как обычно количество различных значений разрядов не превосходит количества сортируемых элементов. Ниже приведен псевдокод цифровой сортировки, которой подается массив <tex> A </tex> размера <tex> m n </tex>-разрядных чисел размера <tex> n m </tex>-разрядных чисел . Сам по себе алгоритм представляет собой цикл по номеру разряда, на каждой итерации которого элементы массива <tex> A </tex> размещаются в нужном порядке во вспомогательном массиве <tex> B </tex>. Для подсчета количества объектов, <tex> i </tex>-й разряд которых одинаковый, а затем и для определения положения объектов в массиве <tex> B </tex> используется вспомогательный массив <tex> 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
=== 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 \geq 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> и выполняется рекурсивное разделение новых частей по следующему разряду в пределах границ корзин, полученных на предыдущем шаге.
Изначально запускаем функцию так <texmath>\mathrm{radixSort(A, 10, A.length- 1, 1)}</texmath>
'''function''' radixSort(int[] A, int l, int r, int d):
'''if''' d > m '''or''' l >= r
'''return'''
j = digit(A[i], d)
c[l + cnt[j]] = A[i]
cnt[j]++--
'''for''' i = l '''to''' r
A[i] = c[i]
==Сложность==
===Сложность LSD-сортировки===
Пусть <tex> m </tex> {{---}} количество разрядов, <tex> n </tex> {{---}} количество объектов, которые нужно отсортировать, <tex> T(n) </tex> {{---}} время работы устойчивой сортировки. Цифровая сортировка выполняет <tex> k </tex> итераций, на каждой из которой выполняется устойчивая сортировка и не более <tex> O(1) </tex> других операций. Следовательно время работы цифровой сортировки {{---}} <tex> O(k T(n)) </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>. Это хорошо тем, что не зависит от числа разрядов.
== Источники информации ==
* [[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-аплет.
* Дональд Кнут Искусство программирования, том 3. Сортировка и поиск
* Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]
[[Категория: Другие сортировки]]
