Алгоритм цифровой сортировки

2018-08-26T17:54:07Z

178.237.190.252: /* Алгоритм LSD */

В этом алгоритме сортировки числа сортируются по разрядам. Существует два варианта Least Significant Digit (LSD) и Most Significant Digit (MSD). При LSD сортировке, сначала сортируются младшие разряды, затем старшие. При MSD сортировке наоборот.

== Алгоритм LSD==
Перед сортировкой необходимо определить 2 величины:

# <tex>width</tex> {{---}} максимальное количество разрядов в сортируемых величинах.
# <tex>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 окажутся пусты, а остальные распределят элементы след. образом:

<tex>list1: 11, 21</tex>

<tex>list4: 24</tex>

<tex>list6: 76</tex>

<tex>list8: 98, 8</tex>

<tex>list9: 9, 59</tex>

''Второй этап'' {{---}} сборка: просто последовательно соединяем один за другим все корзины и располагаем элементы уже в этой последовательности:

<tex>11, 21 (list1), 24(list4), 76(list6), 98, 8(list8), 9, 59(list9)</tex>

Это был один проход алгоритма, соответствующий крайнему правому разряду ключа.
На следующем проходе, элементы из уже обновленной последовательности распределяются по корзинам в соответствии с их вторым(т.е. предпоследним) разрядом и т.д по самого старшего, максимального, <tex>width</tex>-го разряда ключа.

'''Второй проход:'''

''Первый этап'' {{---}} корзины №3, 4, 6, 8 окажутся пусты, а остальные распределят элементы след. образом:

<tex>list0: 8, 9</tex>

<tex>list1: 11</tex>

<tex>list2: 21, 24</tex>

<tex>list5: 59</tex>

<tex>list7: 76</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

Викиконспекты - Вклад участника [ru]

Алгоритм цифровой сортировки