Цифровая сортировка

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

Алгоритм

При цифровой сортировке данные разбиваются на "разряды", после этого данные сортируются какой-либо устойчивой сортировкой по каждому разряду, в порядке от младшего разряда к старшему. Для чисел наиболее часто в качестве устойчивой сортировки применяют сортировку подсчетом.

Сложность

Пусть [math]m[/math] - количество разрядов, n - количество входных данных, T(n) - сложность устойчивой сортировки, тогда сложность цифровой сортировки - [math]О(m*T(n))[/math]. При использовании сортировки подсчетом получаем линейную зависимость.

Псевдокод

 Radix_sort
 for i = 1 to m
    do устойчивая сортировка массива по i-ому разряду

Литература

• Дональд Кнут Искусство программирования, том 3. Сортировка и поиск
• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ

Ссылки

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