1632
правки
Изменения
м
Теперь рассмотрим подробно, что же представляет собой этот алгоритм.
<tex>2. range</tex> - количество возможных значений одного разряда ключа(сортируемого элемента)т.е. мощность используемого алфавита. Сам алгоритм работает следующим образом. Создаются <tex>range</tex> вспомогательных списков - корзин, т.е. на каждое возможное значение разряда элемента по корзине.
rollbackEdits.php mass rollback
== Алгоритм LSD==
Перед сортировкой необходимо определить 2 величины:
# <tex>1. width</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 окажутся пусты, а остальные распределят элементы след. образом:
<tex>list9: 9, 59</tex>
''Второй этап'' {{- --}} сборка: просто последовательно соединяем один за другим все корзины и располагаем элементы уже в этой последовательности:
<tex>11, 21 (list1), 24(list4), 76(list6), 98, 8(list8), 9, 59(list9)</tex>
'''Второй проход:'''
''Первый этап'' {{- --}} корзины №3, 4, 6, 8 окажутся пусты, а остальные распределят элементы след. образом:
<tex>list0: 8, 9</tex>
<tex>list9: 98</tex>
''Второй этап'' {{- --}} собираем и получаем отсортированную по возрастанию последовательность: <tex>8, 9(list0), 11(list1), 21, 24(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
