Поразрядная сортировка (Цифровая сортировка) — алгоритм сортировки за линейное время.

Алгоритм

Алгоритм сортировки.
Числа сортируются по разрядам. Существует два варианта least significant digit (LSD) и most significant digit (MSD). При LSD сортировке, сначала сортируются младшие разряды, затем старшие. При MSD сортировке все наоборот. При LSD сортировке получается следующий порядок: короткие ключи идут раньше длинных, ключи одного размера сортируются по алфавиту, это совпадает с нормальным представлением чисел: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. При MSD сортировке получается алфавитный порядок, который подходит для сортировки строк. Например "b, c, d, e, f, g, h, i, j, ba" отсортируется как "b, ba, c, d, e, f, g, h, i, j". Если MSD применить к числам разной длины, то получим последовательность 1, 10, 2, 3, 4, 5, 6, 7, 8, 9.

При MSD сортировке последовательность сортируется по старшему значимому двоичному разряду так, чтобы все ключи начинающиеся с 0 оказались перед всеми ключами начинающимися с 1. Для этого необходимо найти крайний слева ключ , начинающийся с 1, и крайний справа ключ , начинающийся с 0. После чего и меняются местами, и процесс повторяется, пока не получится . Пусть — множество элементов начинающихся с 0, — множество всех остальных элементов. Применим к поразрядную сортировку (начав теперь со второго бита слева, а не со старшего) до тех пор, пока множество полностью не рассортируется. Затем проделаем то же самое с .

Применение для строк

Вместо сравнения N-й битовой позиции в слове сравнивается N-й байт строки.

Нулевой проход использует только нулевые символы в каждой строке и является корзинной сортировкой по нулевому символу. Эффективная реализация возможна при использовании массива ссылок на строки вместо самих строк, дополнительного массива «границ корзин», инициализируемого частотами встреч символов при первом проходе, они же число элементов в каждой «корзине». При следующем проходе заполняется массив ссылок.

N-й (для N > 0) проход выполняется последовательно над каждой корзиной, полученной на (N - 1)-м проходе, с делением её на «подкорзины». В этом проходе сравниваются N-ные символы каждой строки.

Операция завершается при N, равном максимальной длине строки, или же в ситуации, когда все «подкорзины» получили длину 1.

Литература

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

Ссылки

• Визуализатор1 — Java-аплет.
• Визуализатор2 — Java-аплет.