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

Алгоритм цифровой сортировки (radix sort) использовался в машинах для сортировки перфокарт. В картонных перфокартах специальный перфоратор пробивал дырки. В каждой из 80 колонок были места для 12 прямоугольных дырок.

Сортировочной машине указывали столбец, по которому нужно произвести сортировку, и она раскладывала колоду перфокарт на 10 стопок в зависимости от того, какая из дырок 0-9 была пробита в указанном столбце.

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

Как ни странно, оказывается удобнее начать с младшего разряда, разложив колоду на 10 стопок в зависимости от того, где пробито отверстие в «млад­шем» столбце. Полученные 10 стопок надо после этого сложить в одну в таком порядке: сначала карты с 0, затем карты с 1, и т. д. Получившуюся колоду вновь рассортируем на 10 стопок, но уже в соответствии с разрядом десятков, сложим полученные стопки в одну колоду, и т. д.; если на перфокартах были записаны «d - значные числа, то понадобится d раз воспользоваться сортировочной машиной. На рис. 2.9 показано, как действует этот алгоритм, примененный к семи трёхзначным числам.

Рисунок 2.9 – Пример цифровой сортировки трёхзначных цифр

На рисунке показан исходный порядок чисел, а также после сортировки по третьей, второй и первой цифрам (вертикальные стрелки указывают, по какой цифре производилась сортировка).

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

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

Программу для цифровой сортировки написать легко. Предполагается, что каждый элемент n-элементного массива А состоит из d цифр, причем цифра номер 1 –младший разряд, а цифра номер d – старший.

Листинг 2.10 – Алгоритм цифровой сортировки

Если цифры могут принимать значения от 1 до k, где k не слишком велико, то очевидный выбор – сортировка подсчётом. Для п чисел с d знаками от 0 до k – 1 каждый проход занимает время (n + k); поскольку мы делаем d проходов, время работы цифровой сортировки равно (dn + kd). Если d постоянно и k = О(п), то цифровая сортировка работает за линейное время.

При цифровой сортировке важно правильно выбрать основание системы счисления, поскольку от него зависит размер требуемой дополнительной памя­ти и время работы. Конкретный пример: пусть надо отсортировать миллион 64-битных чисел. Если рассматривать их как четырёхзначные числа в системе счисления с основанием 2¹⁶, то при цифровой сортировке понадобится всего четыре прохода, при использовании в процедуре Counting-Sort массива В размером 2¹⁶ (что немного по сравнению с размером сортируемого массива). Это выгод­но отличается от сортировки сравнением, когда на каждое число приходится по log n  20 операций. К сожалению, цифровая сортировка, опирающаяся на сортировку подсчётом, требует ещё одного массива (того же размера, что и сортируемый) для хранения промежуточных результатов, в то время как мно­гие алгоритмы сортировки сравнением обходятся без этого. Поэтому, если надо экономить память, алгоритм быстрой сортировки может оказаться предпочти­тельнее.