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

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

Алгоритм

Пример цифровой сортировки трехзначных чисел

Имеем множество последовательностей одинаковой длины, состоящих из элементов, на которых задано отношение линейного порядка. Требуется отсортировать эти последовательности в лексикографическом порядке.

По аналогии с разрядами чисел будем называть элементы, из которых состоят сортируемые объекты, разрядами. Сам алгоритм состоит в последовательной сортировке объектов какой-либо устойчивой сортировкой по каждому разряду, в порядке от младшего разряда к старшему, после чего последовательности будут расположены в требуемом порядке.

Примерами объектов, которые удобно разбивать на разряды и сортировать по ним, являются числа и строки.

• Для чисел уже существует понятие разряда, поэтому будем представлять числа как последовательности разрядов. Конечно, в разных системах счисления разряды одного и того же числа отличаются, поэтому перед сортировкой представим числа в удобной для нас системе счисления.

• Строки представляют из себя последовательности символов, поэтому в качестве разрядов в данном случае выступают отдельные символы, сравнение которых обычно происходит по соответствующим им кодам из таблицы кодировок. Для такого разбиения самый младший разряд — последний символ строки.

Для вышеперечисленных объектов наиболее часто в качестве устойчивой сортировки применяют сортировку подсчетом.

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

Докажем, что данный алгоритм работает верно, используя метод математической индукции по номеру разряда. Пусть [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]-м младшим разрядам.

Псевдокод

В качестве примера рассмотрим сортировку чисел. Как говорилось выше, в такой ситуации в качестве устойчивой сортировки применяют сортировку подсчетом, так как обычно количество различных значений разрядов не превосходит количества сортируемых элементов. Ниже приведен псевдокод цифровой сортировки, которой подается массив [math] A [/math] [math] m [/math]-разрядных чисел размера [math] n [/math]. Сам по себе алгоритм представляет собой цикл по номеру разряда, на каждой итерации которого элементы массива [math] A [/math] размещаются в нужном порядке во вспомогательном массиве [math] B [/math]. Для подсчета количества объектов, [math] i [/math]-й разряд которых одинаковый, а затем и для определения положения объектов в массиве [math] B [/math] используется вспомогательный массив [math] C [/math]. Функция [math] digit(x, i) [/math] возвращает [math] i [/math]-й разряд числа [math] x [/math]. Также считаем, что значения разрядов меньше [math] k [/math].

 radixSort(A)
     for i = 1 to m               
         for j = 0 to k - 1                              
             C[j] = 0;                                  
         for j = 0 to n - 1
             d = digit(A[j], i);
             C[d] += 1; 
         for j = 1 to k - 1
             C[j] = C[j] + C[j - 1];
         for j = n - 1 to 0
             d = digit(A[j], i);                             
             B[C[d]] = A[j];               
             C[d] -= 1;
         A = B;

Сложность

Пусть [math] m [/math] — количество разрядов, [math] n [/math] — количество объектов, которые нужно отсортировать, [math] T(n) [/math] — время работы устойчивой сортировки. Цифровая сортировка выполняет [math] k [/math] итераций, на каждой из которой выполняется устойчивая сортировка и не более [math] O(1) [/math] других операций. Следовательно время работы цифровой сортировки — [math] O(k T(n)) [/math].

Рассмотрим отдельно случай сортировки чисел. Пусть в качестве аргумента сортировке передается массив, в котором содержатся [math] n [/math] [math] m [/math]-значных чисел, и каждая цифра может принимать значения от [math] 0 [/math] до [math] k - 1 [/math]. Тогда цифровая сортировка позволяет отсортировать данный массив за время [math] O(m \cdot (n + k)) [/math], если устойчивая сортировка имеет время работы [math] O(n + k) [/math]. Если [math] k [/math] небольшое, то оптимально выбирать в качестве устойчивой сортировки сортировку подсчетом.

Если количество разрядов — константа, а [math] k = O(n) [/math], то сложность цифровой сортировки составляет [math] O(n) [/math], то есть она линейно зависит от количества сортируемых чисел.

Литература

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

Ссылки

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