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

Упражнения

9.2-1 Следуя образцу рис. 9.2., покажите работу алгоритма Counting-Sort для случая к = 7 и А = (7,1, 3,1, 2,4, 5,7,2,4,3).

9.2-2 Докажите, что алгоритм Counting-Sort является устойчивым.

9.2-3 Заменим строку 9 алгоритма Counting-Sort на такую: 9 for j f- 1 to length[A]

Покажите, что алгоритм остаётся правильным. Будет ли он устойчив?

9.2-4 Пусть на выходе алгоритма сортировки надо напечатать элементы входной последовательности в отсортированном порядке. Модифицируйте алгоритм Counting-Sort таким образом, чтобы он делал это, не используя массива В или иных массивов (помимо А и С). (Указание: свяжите в списки элементы массива А с одинаковым значением; где взять место для хранения указателей?).

9.2-5 Дано га целых чисел от 1 до к. Разработайте алгоритм, который подвергает эти данные предварительной обработке, а затем за время 0(1) отвечает на любой вопрос типа «сколько чисел из данного набора лежит между а и 6?». Время на предварительную обработку должно быть О (га + к).

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

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

Сортировочной машине указывали столбец, по которому нужно

Рис. 9.3 Цифровая сортировка последовательности из семи трёхзначных чисел. На вход подаются числа первого столбца. Далее показан порядок чисел после сортировки по третьей, второй и первой цифрам (вертикальные стрелки указывают, по какой цифре производилась сортировка).

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

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

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

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

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

этого, однако, можно просто трижды отсортировать массив дат с помощью устойчивого алгоритма: сначала по дням, потом по месяцам, потом по годам.

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

Radix-Sort (A, d) 1 for г +- 1 to d

Правильность алгоритма цифровой сортировки доказывается индукцией по номеру разряда (см. упр. 9.3-3). Время работы зависит от времени работы выбранного устойчивого алгоритма. Если цифры могут принимать значения от 1 до /г, где к не слишком велико, то очевидный выбор - сортировка подсчётом. Для га чисел с d знаками от 0 до к - 1 каждый проход занимает время 0(га + к); поскольку мы делаем d проходов, время работы цифровой сортировки равно ®{dn-\-kd). Если d постоянно и к = О(п), то цифровая сортировка работает за линейное время.

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

Упражнения

9.3-1 Следуя образцу рис. 9.3, покажите, как происходит цифровая сортировка (по алфавиту) английских слов COW, DOG, SEA,

RUG, ROW, MOB, BOX, TAB, BAR, EAR, TAR, DIG, BIG, TEA, NOW, FOX.

2

do отсортировать массив А устойчивым

алгоритмом по значению цифры номер г