53
правки
Изменения
м
Нет описания правки
Перед сортировкой необходимо определить 2 величины:
# <tex>1. width</tex> {{- --}} максимальное количество разрядов в сортируемых величинах. # <tex>2. range</tex> {{- --}} количество возможных значений одного разряда ключа(сортируемого элемента)т.е. , то есть мощность используемого алфавита.
Сам алгоритм работает следующим образом. Создаются <tex>range</tex> вспомогательных списков - корзин, т.е. на каждое возможное значение разряда элемента по корзине.
'''Первый проход:'''
''Первый этап'' {{- --}} распределение по корзинам и на первом проходе элементы исходной последовательности помещаются в эти корзины по их младшему разряду, т.е. по самому правому символу. Какой этот самый младший разряд у элемента, в такую корзину этот элемент и помещается.
Например, пусть имеем исходную последовательность из <tex>{11, 24, 9, 59, 21, 98, 76, 8}</tex>, для которой определяем <tex>width</tex> = 2, <tex>range</tex> = 10, поэтому будет 10 корзин: <tex>list0, list1..., list9</tex>. Тогда на первом проходе корзины №0, 2, 3, 5, 7 окажутся пусты, а остальные распределят элементы след. образом:
'''Второй проход:'''
''Первый этап'' {{- --}} корзины №3, 4, 6, 8 окажутся пусты, а остальные распределят элементы след. образом:
<tex>list0: 8, 9</tex>
<tex>list9: 98</tex>
''Второй этап'' {{- --}} собираем и получаем отсортированную по возрастанию последовательность: <tex>8, 9(list0), 11(list1), 21(list2), 59(list5), 76(list7), 98(list 9)</tex>
== Время работы ==
Алгоритм цифровой сортировки работает за линейное время - <tex>O(k(n + |A|))</tex>, где <tex>|A|</tex> {{- --}} мощность алфавита(<tex>range</tex>), <tex>k</tex> {{--- }} максимальная длина строки(<tex>width</tex>), <tex>n</tex> {{--- }} количество сортируемых строк.
== Применение ==
Алгоритм цифровой сортировки позволяет строить суффиксный массив за <tex>O(n^2)</tex>, где <tex>n</tex> {{- --}} длина строки.
== Источник ==
Дональд Кнут Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — С. 824. — ISBN 5-8459-0082-4
