9.65. Добавить деструктор, конструктор копирования и перегруженную операцию присваивания в реализации биномиальной очереди (программы 9.13-9.16), приведенные в тексте книги, с целью разработки реализации АТД первого класса из упражнения 9.43. Написать программу-драйвер, которая сможет протестировать полученные интерфейс и реализацию.

9.66. Эмпирическим путем сравнить биномиальные очереди с сортирующими деревьями с целью их использования в качестве основы для сортировки (как в профамме 9.6) произвольно упорядоченных ключей при 7V = 1000, 10 *, 10 и 10 Совет: см. упражнение 9.37.

9.67. Разработать метод обменной сортировки, аналогичной сортирующему дереву, но основанной на биномиальных очередях. Совет: см. упражнение 9.37.

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

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

Зрения. Методы сортировки, построенные на обработке чисел по одной порции за раз, называются поразрядными (radix) методами сортировки. Эти методы не только выполняют сравнение ключей: они обрабатывают и сравнивают соответствующие части ключей.

Алгоритмы поразрядной сортировки рассматривают ключи как числа, представленные в системе счисления с основанием R при различных значениях R (основание системы счисления), и работают с отдельными цифрами чисел. Например, если машина в почтовом отделении обрабатывает пачку пакетов, каждый из которых помечен десятичным числом из пяти цифр, она распределяет эту пачку на десять отдельных стопок: в одной стопке находятся пакеты, номера которых начинаются с О, в другой находятся пакеты с номерами, начинающимися с 1, в третьей - с 2 и т.д. При необходимости каждая из стопок может быть подвергнута отдельной обработке с применением того же метода к следующей цифре или более простого метода, если в стопке осталось всего лишь несколько пакетов. Если бы перед нами стояла задача распределения пакета в стопки в порядке от О до 9 и в том порядке отсортировать каждую стопку, то будет упорядочен весь пакет. Эта процедура является простым примером поразрядной сортировки с R =10, именно такой метод сортировки чаще всего выбирается как наиболее подходящий в различных практических приложениях, в которых ключами являются десятичные числа, содержащие от 5 до 10 цифр, например, почтовые коды, телефонные номера или коды службы социальной защиты. Подробно этот метод рассматривается в разделе 10.3.

Для различных приложений подходят различные основания системы счисления R. В этой главе мы главным образом сосредоточимся на ключах, представленных в виде целых чисел и строк, для сортировки которых широко применяются методы поразрядной сортировки. Для целых чисел в силу того обстоятельства, что они представлены в компьютерах в виде двоичных чисел, мы чаще других будем выбирать для работы /? = 2 или одну из степеней числа 2, поскольку такой выбор позволяет разложить ключи на независимые друг от друга порции. Что касается ключей, в состав которых входят строки символов, мы используем /? = 128 или R = 256, приравнивающий основание системы счисления к размеру байта. Помимо такого рода прямых приложений мы можем в конечном итоге рассматривать фактически все, что может быть представлено в цифровом компьютере как двоичное число, благодаря чему мы имеем возможность сориентировать многие приложения сортировки на использование различных типов ключей с тем, чтобы сделать возможной использование поразрядной сортировки для упорядочения ключей, представляющих собой двоичные числа.

В основе алгоритмов поразрядной сортировки лежит абстрактная операция извлечь из ключа /-ю цифру. К счастью, в С++ существуют низкоуровневые операции, благодаря которым можно реализовать такие действия просто и эффективно. Этот факт очень важен, поскольку многие другие языки программирования (например, Pascal), поощряя написание машинно-независимых программ, намеренно создают трудности в написании программ, которые зависят от способа представления чисел в конкретной машине. В таких языках достаточно трудно реализовать многие типы методы побитовых манипуляций, которые хорошо подходят для большинства компьютеров. В частности, на текущий момент поразрядную сортировку можно считать