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

В этом алгоритме сортировки числа сортируются по разрядам. Существует два варианта [math]least significant digit (LSD)[/math] и [math]most significant digit (MSD)[/math]. При [math]LSD[/math] сортировке, сначала сортируются младшие разряды, затем старшие. При [math]MSD[/math] сортировке все наоборот. При [math]LSD[/math] сортировке получается следующий порядок: короткие ключи идут раньше длинных, ключи одного размера сортируются по алфавиту. При [math]MSD[/math] сортировке получается алфавитный порядок, который подходит для сортировки строк.

Алгоритм LSD

Теперь рассмотрим подробно, что же представляет собой этот алгоритм.

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

[math]1. width[/math] - максимальное количество разрядов в сортируемых величинах

[math]2. 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]. Тогда на первом проходе корзины №2, 3, 5, 7 окажутся пусты, а остальные распределят элементы след. образом:

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

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

[math]list4: 24[/math]

[math]list6: 76[/math]

[math]list8: 98[/math]

[math]list9: 59[/math]

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

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

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

Время работы

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

Применение

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

Источник

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