1632
правки
Изменения
м
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
j = digit(A[i], d)
c[l + cnt[j]] = A[i]
cnt[j]++--
'''for''' i = l '''to''' r
A[i] = c[i]
Пусть значения разрядов меньше <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-сортировки, при которой рекурсивный процесс останавливается при небольших размерах текущего кармана, и вызывается более быстрая сортировка , основанная на сравнениях (например, сортировка вставками).
== См. также ==
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]
[[Категория: Другие сортировки]]
