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

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

Существуют два принципиально различных базовых подхода к поразрядной сортировке. Первый класс методов составляют алгоритмы, которые анализируют значение цифр в ключах в направлении слева направо, при этом первыми обрабатываются наиболее значащие цифры. Такие методы в общем случае называются поразрядной сортировкой MSD (most significant digit radix sort - Поразрядная сортировка сначала по старшей цифре). Поразрядная сортировка MSD привлекательна прежде всего тем, что в этом случае анализируется минимальный объем информации, необходимый для выполнения сортировки (см. рис. 10.1). Поразрядная сортировка MSD обобщает понятие быстрой сортировки, поскольку она выполняется за счет разделения сортируемого файла в соответствии со старшими цифрами

ключей, после чего тот же метод применяется к g .015583409 ,0 подфайлам в режиме рекурсии. В самом деле, в 353336668 159072306 1590 условиях, когда в качестве основания системы [ 318693642 ! 159369371 !l593 счисления выбрана 2, мы реализуем поразрядную .015583409 . 269971047 .2 сортировку MSD тем же способом, что и быструю ,159369371 .318693642 . 31 сортировку. Во втором классе методов поразряд- .691004885 .353336658 . 35 ной сортировки используется другой принцип: они .899854354 . 396465048 . 39 анализируют цифры ключей в направлении справа .159072306 . 538069659 .5 налево, работая с сначала с наименее значащей .604144269 .604144269 . 60

, . с ,269971047 .691004885 .69

цифрой. Эти методы в общем случае называются i

. тспл / г л- .538069659 . 899854354 .8

поразрядной сортировкой LSD (least significant digit radix

sort - Поразрядная сортировка сначала no младшей РИСУНОК 10.1. ПОРАЗРЯДНАЯ

цифре). Поразрядная сортировка LSD в какой-то СОРТИРОВКА

Несмотря на то что между О и 1 в степени противоречит интуиции, поскольку основ- ,

г f J > J рассматриваемом списке находятся

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

(столбец справа).

10.1. Биты, байты и слова

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

Определение 10.1. Байт представляет собой последовательность битов фиксированной длины, строка есть последовательность байтов переменной длины, слово есть последовательность байтов фиксированной длины.

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

Типичная машина оперирует 8-разрядными байтами и 32- и 64-разрядными словами (фактические значения можно найти в заголовочном файле <limits.h>), однако удобнее иметь возможность рассматривать также и некоторые другие размеры байтов и слов (в общем случае небольшие кратные целые конструктивных машинных размеров или их части). Мы используем в качестве числа разрядов в слове и числа разрядов в байте машинно-зависимые и зависимые от приложений константы, например:

const int bitsword = 32; const int bitsbyte = 8;

const int bytesword = bitsword/bitsbyte; const int R=l bitsbyte;

В эти определения для последующего использования, когда мы начнем рассматривать поразрядные сортировки, включается также константа R, представляющая число различных значений байтов. Пользуясь этими определениями мы в общем случае предполагаем, что bitsword является кратным bitsbyte, что число битов в машинном слове не меньше (обычно равно) bitsword, и что байты допускают индивидуальную адресацию. В различных компьютерах реализованы различные соглашения, касающиеся ссылок на их биты и байты, для целей наших рассуждений мы будем считать, что биты в слове перенумерованы слева направо, от О до bitsword-1, и байты в слове перенумерованы слева направо, от О до bytesword-1. В обоих случаях мы полагаем, что нумерация производится от наибольшего значения к наименьшему значению.

В большинстве компьютеров реализованы битовые операции и (and) и сдвиг (shift), которыми мы можем воспользоваться для извлечения отдельных байтов из слов. В С++ мы можем прямо написать операции извлечения 5-ого байта из двоичного А слова следующим образом:

inline int digit (long A, int B)

{ return (A bitsbyte*(bytesword-B-1) & (R-1); }

Например, данная макрокоманда извлекает байт 2 (третий байт) 32-разрядного числа путем сдвига вправо на 32 - 3 * 8 = 8 позиций с последующим использованием маски 00000000000000000000000011111111 с целью обнуления всех разрядов за исключением искомого байта, занимающего 8 разрядов справа.

Многие машины организованы таким образом, что в качестве размера байта взято основание одной из систем счисления, в силу чего обеспечивается быстрая выборка нужных битов в рамках одного доступа. Эта операция непосредственно поддерживается С++ строками в С-стиле:

inline int digit (char* A, int B) { return A[B]; }

Если мы используем структуру-оболочку, подобную рассмотренной в разделе 6.8, мы будем записывать:

inline int digit(Items A, int B) { return A.str[B]; }

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

На другом уровне абстракции, несколько отличном от рассматриваемого, мы можем представлять себе ключи как числа и байты как цифры. Если выбрано (ключ представлен как) число, то базовая операция, необходимая для реализации поразрядной сортировки есть извлечение из числа цифры. Когда мы выбираем в качестве основания для системы счисления степень 2, цифрами являются группы битов, к которым мы легко можем получить доступ используя рассмотренные выше макросы. В самом деле, основной причиной того, что в качестве основания системы счисления используется степень 2 является то, что операция доступа к группе битов не требует больших затрат. В некоторых вычислительных средах можно выбирать другие основания систем счисления. Например, если а есть положительное целое число, то Ь-я цифра представления а в системе счисления R есть

a/>?*J mod R.

На машинах, предназначенных для высокопроизводительных числовых вычисле-ний эти вычисления могут выполняться для произвольного значения R так же быстро, как и для случая Л = 2.

Еще одна точка зрения призывает рассматривать ключи как числа в диапазоне от О до 1, при этом подразумевается, что десятичная точка находится слева, как показано на рис. 10.1. В этом случае Ь-ой цифрой числа а будет

aR\ mod R.

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