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

Пример цифровой сортировки

Цифровая сортировка — один из алгоритмов сортировки, использующих внутреннюю структуру сортируемых объектов.

Алгоритм

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

Корректность алгоритма

Докажем, что данный алгоритм работает верно, используя метод математической индукции по номеру разряда. Для простоты рассуждений будем предполагать, что объекты сортируются по неубыванию. Пусть [math] n [/math] — количество разрядов в сортируемых объектах.

• База: [math] n = 1 [/math]. Очевидно, что алгоритм работает верно, потому что в таком случае мы просто сортируем младшие разряды какой-то заранее выбранной стабильной сортировкой.
• Переход: Пусть для [math] n = k [/math] алгоритм правильно отсортировал элементы по [math] k [/math] младшим разрядам. Покажем, что в таком случае, при сортировке по [math] (k + 1) [/math]-ому разряду, объекты также будут отсортированы в правильном порядке. Вспомогательная сортировка разобьет все объекты на группы, в которых [math] (k + 1) [/math]-ый разряд объектов одинаковый. Рассмотрим такие группы. Для сортировки по отдельным разрядам мы используем стабильную сортировку, следовательно порядок объектов с одинаковым [math] (k + 1) [/math]-ым разрядом не изменился. Но по предположению индукции по предыдущим [math] k [/math] разрядам объекты были отсортированы правильно, и поэтому в каждой такой группе объекты будут отсортированы верно. Также верно, что сами группы находятся в правильном относительно друг друга порядке, а следовательно и все элементы отсортированы правильно по [math] (k + 1) [/math]-ым младшим разрядам.

Псевдокод

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

Сложность

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

Литература

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

Ссылки

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