Поразрядная сортировка

Поразрядная сортировка (англ. radix sort) — это алгоритм сортировки данных, который обрабатывает элементы по отдельным разрядам (цифрам) их представления. В отличие от алгоритмов сравнения (например, быстрой сортировки или сортировки слиянием), поразрядная сортировка не сравнивает элементы напрямую, а группирует их по значениям каждого разряда, от младшего к старшему или наоборот. Это позволяет достичь линейной временной сложности O(n·k), где n — количество элементов, а k — количество разрядов, при условии, что разрядность элементов ограничена. Алгоритм особенно эффективен для сортировки целых чисел, строк фиксированной длины и других данных, которые можно представить в виде последовательности цифр в системе счисления с небольшим основанием.

История

Идея поразрядной сортировки восходит к началу XX века. Первое известное описание алгоритма было опубликовано в 1887 году американским инженером Германом Холлеритом (Herman Hollerith) для сортировки перфокарт. Холлерит разработал табулятор, который использовал механический считыватель для группировки карт по отверстиям, соответствующим определённым разрядам. Этот метод лёг в основу первых машин для обработки данных в переписи населения США 1890 года.

В 1954 году американский математик Гарольд Сьюард (Harold Seward) формализовал поразрядную сортировку в контексте компьютерных вычислений, предложив её реализацию для машин с магнитной лентой. В 1960-х годах алгоритм получил широкое распространение в системах управления базами данных и пакетной обработки, где требовалась сортировка больших объёмов числовых данных. С развитием языков программирования и архитектур компьютеров поразрядная сортировка стала применяться в специализированных библиотеках, например, в стандартной библиотеке языка C++ (функция std::sort в некоторых реализациях использует гибридные подходы, включающие поразрядную сортировку для целых чисел).

Принцип работы

Поразрядная сортировка основана на идее обработки чисел по разрядам. Каждый разряд рассматривается как ключ сортировки, а алгоритм последовательно применяет устойчивую сортировку (например, сортировку подсчётом) для каждого разряда. Устойчивость означает, что элементы с одинаковыми значениями текущего разряда сохраняют свой относительный порядок, установленный на предыдущих шагах.

Основные варианты

Существует два основных подхода к поразрядной сортировке:

1. LSD (Least Significant Digit) — сортировка от младшего разряда к старшему. Начинается с самого правого (младшего) разряда числа. После обработки всех разрядов элементы оказываются упорядоченными полностью. LSD-алгоритм проще в реализации и чаще используется для целых чисел фиксированной длины.
2. MSD (Most Significant Digit) — сортировка от старшего разряда к младшему. Начинается с самого левого (старшего) разряда. После обработки первого разряда элементы группируются по значению этого разряда, и каждая группа сортируется рекурсивно по следующему разряду. MSD-алгоритм может быть быстрее для строк переменной длины, но требует рекурсивной обработки и дополнительной памяти для хранения промежуточных результатов.

Алгоритм LSD (на примере десятичных целых чисел)

1. Определить максимальное количество разрядов k среди всех чисел (например, для чисел от 0 до 999 — k=3).
2. Для каждого разряда от 0 до k-1 (начиная с младшего):

• Создать 10 пустых корзин (по числу цифр от 0 до 9).
• Распределить все числа по корзинам в соответствии с цифрой в текущем разряде.
• Собрать числа из корзин в исходный массив, сохраняя порядок внутри каждой корзины.

1. После обработки всех разрядов массив отсортирован.

Пример

Исходный массив: [170, 45, 75, 90, 2, 802, 24, 66]

• Разряд единиц (LSD): корзины по цифре 0: 170, 90; цифра 2: 2, 802; цифра 4: 24; цифра 5: 45, 75; цифра 6: 66. Результат: [170, 90, 2, 802, 24, 45, 75, 66].
• Разряд десятков: корзины по цифре 0: 2, 802; цифра 2: 24; цифра 4: 45; цифра 6: 66; цифра 7: 170, 75; цифра 9: 90. Результат: [2, 802, 24, 45, 66, 170, 75, 90].
• Разряд сотен: корзины по цифре 0: 2, 24, 45, 66, 75, 90; цифра 1: 170; цифра 8: 802. Результат: [2, 24, 45, 66, 75, 90, 170, 802].

Характеристики

Временная сложность

• Лучший случай: O(n·k), где n — количество элементов, k — количество разрядов. Если k значительно меньше n, сложность приближается к линейной.
• Худший случай: O(n·k) — алгоритм не зависит от начального порядка данных, поэтому худший случай совпадает с лучшим.
• Средний случай: O(n·k).

Пространственная сложность

• Дополнительная память: O(n + b), где b — основание системы счисления (например, 10 для десятичных чисел). Для хранения корзин требуется массив размером n и вспомогательный массив для подсчёта элементов в каждой корзине.
• Рекурсивная версия MSD может потребовать дополнительной памяти для стека вызовов, но в среднем её глубина не превышает k.

Устойчивость

Поразрядная сортировка является устойчивым алгоритмом, если для каждого разряда используется устойчивая внутренняя сортировка (например, сортировка подсчётом). Это свойство важно для сохранения порядка элементов с одинаковыми ключами.

Применение

Поразрядная сортировка применяется в задачах, где требуется высокая скорость сортировки больших массивов целых чисел или строк фиксированной длины. Основные области использования:

• Обработка баз данных: сортировка записей по числовым идентификаторам, датам или другим ключам с фиксированным форматом.
• Компьютерная графика: сортировка пикселей по цветовым компонентам (RGB) для построения гистограмм или фильтрации.
• Сетевые протоколы: сортировка IP-адресов (32-битные числа) для маршрутизации или анализа трафика.
• Сжатие данных: в алгоритмах, где требуется упорядочивание символов или кодов (например, в кодировании Хаффмана).
• Научные вычисления: сортировка больших массивов экспериментальных данных, представленных в виде чисел с плавающей запятой (при приведении к целочисленному представлению).

Примеры реализации

• В стандартной библиотеке языка C++ (GCC) функция std::sort для целочисленных типов может использовать поразрядную сортировку в качестве внутреннего этапа при оптимизации.
• В языке Python реализация поразрядной сортировки доступна через сторонние библиотеки, например, numpy (функция numpy.sort с параметром kind='radix').
• В языке Java алгоритм применяется в классе Arrays для сортировки примитивных типов (например, Arrays.sort(int[]) использует поразрядную сортировку LSD для массивов большого размера).

Сравнение с другими алгоритмами

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

• Быстрая сортировка: O(n log n) в среднем, но может деградировать до O(n²) в худшем случае. Поразрядная сортировка стабильнее по времени, но требует больше памяти.
• Сортировка слиянием: O(n log n) с дополнительной памятью O(n). Поразрядная сортировка быстрее для больших n, но менее гибка.
• Сортировка подсчётом: O(n + k) для целых чисел с малым диапазоном. Поразрядная сортировка расширяет этот подход на большие диапазоны за счёт разбиения на разряды.

Интересные факты

• Поразрядная сортировка может быть адаптирована для сортировки чисел с плавающей запятой, если интерпретировать их битовое представление как целые числа (например, IEEE 754). Однако для отрицательных чисел требуется дополнительное преобразование, так как их битовое представление не монотонно.
• В некоторых реализациях LSD-сортировка использует основание 256 (байтовое представление), что позволяет обрабатывать числа за 4 прохода (для 32-битных целых чисел) или 8 проходов (для 64-битных).
• Алгоритм MSD может быть реализован без рекурсии с использованием очередей или стеков, что снижает накладные расходы на управление памятью.

Критика

Основные недостатки поразрядной сортировки связаны с её ограничениями:

• Зависимость от представления данных: алгоритм не работает напрямую с произвольными типами данных (например, строками переменной длины или объектами), если не определён способ их разрядного разбиения.
• Потребление памяти: для хранения корзин требуется дополнительная память, что может быть критично для встраиваемых систем или устройств с ограниченными ресурсами.
• Неэффективность для малых массивов: для небольших наборов данных (n < 100) накладные расходы на создание корзин и подсчёт могут превышать время работы алгоритмов сравнения.

Источники

• Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed.). Addison-Wesley.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
• Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley.
• Hollerith, H. (1887). Art of Compiling Statistics. U.S. Patent 395,782.