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

Определение 10.2. Ключ есть число в системе счисления с основанием R, цифры которого пронумерованы слева (начиная с 0).

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

Мы полагаем, что ключи достаточно длинные, так что операция извлечения из них битов имеет смысл. Если же ключи короткие, то мы можем применять метод подсчета индексных ключей, рассмотренных в главе 6. Напомним, что этот метод позволяет сортировать yv ключей, представляющие собой целые числа, принимающие значения в диапазоне от О до 7? - 1 за линейное время, используя для этой цели одну вспомогательную таблицу размером R для расчетов и другую таблицу размером для переупорядочения N записей. Следовательно, если мы можем себе позволить поддержку таблицы размером 2 , то сортировку w-разрядных ключей легко выполнить за линейное время. В самом деле, расчеты, связанные подсчетом индексных ключей, лежат в основе базовых методов поразрядной сортировки MSD и LSD. Поразрядная сортировка вступает на передний план, когда ключи обладают достаточной длиной (скажем, W = 64), когда использование таблицы размером 2 не является целесообразным.

Упражнения

t>10.1. Сколько нужно цифр для представления 32-разрядного числа в системе счисления, основанием которой является 256? Опишите, как можно извлечь каждую цифру этого числа. Ответьте на этот вопрос для случая, когда основанием системы счисления будет число 2.

t>10.2. Для N = 10 10 и 10 дать наименьший размер байта, который позволит представить любое число в диапазоне от О до yV в виде слова из 4 байтов.

о 10.3. Перегрузить операцию operatoK, используя абстракцию digit (чтобы, например, можно было выполнять эмпирические исследования, сравнивая алгоритмы из глав 6 и.9 с методами, описанными в данной главе, используя одни и те же данные).

о 10.4. Разработать и выполнить эксперимент, сравнивающий затраты ресурсов на извлечение цифр с использованием в одном случае операции сдвига и в другом случае - арифметических операций, реализованных на вашей машине. Сколько цифр вы можете извлечь за секунду, используя каждый из двух этих методов? Указание: будьте осторожны, ваш компилятор может преобразовать арифметические операции в операции сдвига битов и наоборот.

10.5. Напишите программу, которая при заданном наборе произвольных десятичных чисел (Л = 10), равномерно распределенных на интервале от О до 1, будет вычислять количество операций сравнения чисел, необходимых для их сортировки в смысле рис. 10.1. Выполните эту программу для N = 10, Ю*, 10 и 10

10.6. Выполнить упражнение 10.5 для R = 2, используя 32-разрядные величины.

10.7. Выполнить упражнение 10.5 для случае, когда числа подчиняются распределению Гаусса.

10.2. Двоичная быстрая сортировка

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

Программа 10.1 представляет полную реализацию этого метода. Применяемый в ней процесс разбиения по существу лишь немногим отличается от разбиения, реализованного в программе 7.2, за исключением того, что в рассматриваемом случае в качестве разделяющего элемента используется число 2*, а не некоторый ключ из файла. Поскольку числа 2* может и не быть в файле, то нет гарантии того, что конкретный элемент будет помещен в свою окончательную позицию в процессе разбиения. Рассматриваемый алгоритм отличается от алгоритма быстрой сортировки, поскольку рекурсивные вызовы выполняются для ключей, имеющим на 1 бит меньше. Это различие существенно влияет на эффективность алгоритма. Например, если имеет место вырожденное разбиение файла из Л элементов, то произойдет рекурсивный вызов для подфайла размером Л для ключей, имеющим размер на 1 разряд меньше. Следовательно, число таких вызовов ограничено количеством разрядов в ключе. В противоположность этому, последовательное использование разделяющих значений, взятых не из самого файла в условиях стандартной быстрой сортировки может привести к возникновению бесконечного рекурсивного цикла.

Как и в случае стандартной быстрой сортировки, возможны различные варианты реализации внутренних циклов. В профамме проверка, не пересеклись ли значения указателей, включена в оба внутренних цикла. Такая проверка приводит к дополнительному обмену местами для случая, когда / =J, чего можно избежать путем применения break, что, собственно говоря, и сделано в программе 7.2, хотя в рассматриваемом случае обмен элемента a[i] на самого себя вполне безобиден. Другой альтернативой является использование служебной метки.

Программа 10.1. Двоичная быстрая сортировка

Эта программа производит разделение файла по старшим разрядам, после чего выполняет рекурсивную сортировку полученных подфайлов. Переменная d фиксирует анализируемый бит, начиная с О (крайний левый). Процесс разделение заканчивается, когда j становится равным i, т.е. когда все элементы справа от а[1] имеют 1 в d-й позиции, а все элементы слева от имеют О в cf-й позиции. Сам элемент а[1] имеет в d-й позиции 1, если только у всех ключей файла в позиции d не стоит 0. Дополнительная проверка, выполняемая непосредственно по окончании цикла, охватывает и этот случай.

template <class Item> void quicksortB (Item a[], { int i = 1, j = r; if (r <= 1 II d > while (j != i) {

while (digit (a [i] , d) while (digit (a[j] , d) exch(ati], a[j]);

if (digit(a[r], d) quicksortB(a, 1, quicksortB(a, j,

int 1, int r, int d) bitsword) return;

&& &&

(i (j

j)) i))

i++; j -;

== 0) j++; j-1, d+1); r, d+1);

template <class Item> void sort(Item a[], int 1, int r) { quicksortB(a, 1, r, 0); }

Рисунок 10.2 дает описание работы программы 10.1 на примере простого учебного файла и сравнивает ее с быстрой сортировкой, представленной на рис. 7.1. Этот рисунок показывает, каким является движение данных, но не объясняет, почему производятся те или иные перемещения - это зависит от двоичного представления соответствующих ключей. Более подробное представление этого же примера дано на рис. 10.3. В рамках этого примера предполагается, что буквы кодируются 5-разрядными кодами, при этом для /-Й буквы алфавита используется двоичное представление числа /. Подобное кодирование представляет собой упрощенную версию настоящих кодов символов, для которых используется большее число битов (7.8 и даже 16) с тем, чтобы охватить большее число символов (буквы верхнего и нижнего регистров, числа и специальные символы).

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

А S о R Т I А Е о L М I

А Е А Е G

NGEXAMPL I NGEAXTPR S Т Р R S R Р т Р R S R S

I N М L О I N М L О L М N О N О

Е Е G Е Е G Е Е ЕЕ

EEG I LMNOPRSTX

РИСУНОК 10.2. ПРИМЕР ДВОИЧНОЙ БЫСТРОЙ СОРТИРОВКИ

Разделение по старшему разряду еще не гарантирует того, что хотя бы одно значение станет на свое окончательное место, оно лишь обеспечивает, что все ключи с Ов старших разрядах предшествуют ключам с 1 в старших разрядах. Мы можем сравнить эту диаграмму с рис. 7.1, иллюстрирующим быструю сортировку, хотя то, как выполняется метод разделения, совершенно непонятен, если для ключей не выбран двоичный метод представления. На рис. 10.3 приводятся подробности, благодаря которым становится ясно, по каким позициям производится разделение.