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

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

Алгоритм LSD

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

1. [math]width[/math] — максимальное количество разрядов в сортируемых величинах.
2. [math]range[/math] — количество возможных значений одного разряда ключа (сортируемого элемента), то есть мощность используемого алфавита.

Создаются [math]range[/math] вспомогательных списков-корзин, т.е. на каждое возможное значение разряда элемента по корзине.

Первый проход:

Первый этап — распределение по корзинам и на первом проходе элементы исходной последовательности помещаются в эти корзины по их младшему разряду, т.е. по самому правому символу. Какой этот самый младший разряд у элемента, в такую корзину этот элемент и помещается.

Например, пусть имеем исходную последовательность из [math]{11, 24, 9, 59, 21, 98, 76, 8}[/math], для которой определяем [math]width[/math] = 2, [math]range[/math] = 10, поэтому будет 10 корзин: [math]list0, list1..., list9[/math]. Тогда на первом проходе корзины №0, 2, 3, 5, 7 окажутся пусты, а остальные распределят элементы след. образом:

[math]list1: 11, 21[/math]

[math]list4: 24[/math]

[math]list6: 76[/math]

[math]list8: 98, 8[/math]

[math]list9: 9, 59[/math]

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

[math]11, 21 (list1), 24(list4), 76(list6), 98, 8(list8), 9, 59(list9)[/math]

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

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

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

[math]list0: 8, 9[/math]

[math]list1: 11[/math]

[math]list2: 21, 24[/math]

[math]list5: 59[/math]

[math]list7: 76[/math]

[math]list9: 98[/math]

Второй этап — собираем и получаем отсортированную по возрастанию последовательность: [math]8, 9(list0), 11(list1), 21(list2), 59(list5), 76(list7), 98(list 9)[/math]

Время работы

Алгоритм цифровой сортировки работает за линейное время - [math]O(k(n + |A|))[/math], где [math]|A|[/math] — мощность алфавита([math]range[/math]), [math]k[/math] — максимальная длина строки([math]width[/math]), [math]n[/math] — количество сортируемых строк.

Применение

Алгоритм цифровой сортировки позволяет строить суффиксный массив за [math]O(n^2)[/math], где [math]n[/math] — длина строки.

Источник

Дональд Кнут Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — С. 824. — ISBN 5-8459-0082-4