Программа 10.3. Трехпутевая поразрядная быстрая сортировка

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

#define ch(A) digit(A, d)

template <class Item>

{

int i, j, k, p, q; int v;

if (r-1 <= M) { insertion (a, 1, r) ; return; }

v = ch(a[r]); i = 1-1; j = r; p = 1-1; q = r; while (i < j)

{

while (ch(a[++i]) < v) ;

while (v < ch(a[- - j])) if (j == 1) break;

if (i > j) break;

exch(a[i], a[j]);

if (ch(a[i])==v) { p++; exch(a[p], a[i]); }

if (v==ch(a[j])) { q--; exch(a[j], a[q]); }

}

if (p == q)

{ if (v != "\0") quicksortX(a_, 1, r, d+1) ; return; }

if (ch(a[i]) < v) i++;

for (k = 1; k <= p; k++, j--) exch(a[k], a[j]);

for (k = r; k >= q; k--_, i++) exch(a[k], a[i]);

quicksortX(a, 1, j, d) ;

if ((i == r) && (ch(a[i]) == v)) i++;

if (v != "\0") quicksortX(a_, j+1, i-1, d+1) ; quicksortX(a, i, r, d) ;

}

РИСУНОК 10.12. РЕКУРСИВНАЯ СТРУКТУРА ТРЕХПУТЕВОЙ ПОРАЗРЯДНОЙ БЫСТРОЙ СОРТИРОВКИ

Представленная на диаграмме комбинация двоичного и троичного деревьев соответствует подстановке 26-путевых узлов в двоичное дерево, изображенное на рис. 10.10, троичных деревьев поиска, как показано на рис. 10.13. Любой путь от корня на нижний уровень дерева, который жанчивается средней связью, определяет ключ файла, задаваемый символами, охваченными средними связями на этом пути. В диаграмме, показанной на рис. 10.10, имеется 1035 пустых связей, которые не отображены на ней, что касается рассматриваемой диаграммы, то все 155 пустых связей, которыми обладает это дерево, на диаграмме показаны. Каждая пустая связь соответствует пустой корзине, так что это различие показывает, как трехпутевой разбиение может существенно сократить число пустых корзин, которые появляются во время поразрядной сортировки MSD.

Рассмотрим случай, когда ключи имеют большую длину (для простоты предположим, что длина ключей фиксирована) и в то же время по большей части старшие байты одинаковы. В подобного рода ситуациях время выполнения обычной быстрой сортировки пропорционально длине слова, помноженной на 27Vln7V, тогда как время выполнения ее поразрядной версии пропорционально N, умноженному на длину слова (чтобы обнаружить все равные между собой старшие байты) плюс 2N\r\N (затрачивается на сортировку более коротких ключей). Иначе говоря, этот метод работает в ln/V раз быстрее, чем обычная быстрая сортировка, если принимать во внимание только стоимость операций сравнения. Для ключей, используемых в сортировочных приложениях на практике, характеристики, подобные полученным в условиях рас-смотренного выше искусственного примера, не являются чем-то необычным (см. упражнение 10.25).

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

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

Трехпутевая быстрая сортировка успешно применяется и в тех случаях, когда сортируемыми ключами являются векторы (как в математическом смысле, так и в смысле стандартной библиотеки шаблонов C++. Другими словами, если ключи составлены из независимых компонентов (каждый компонент сам по себе независимый ключ), мы имеем возможность переупорядочить записи таким образом, что они будут располагаться в порядке следования первых компонентов ключей и в порядке следования вторых компонентов ключей в тех случаях, когда равны их первые компоненты и т.д. Мы можем рассматривать сортировку векторов как обобщенный вид поразрядной сортировки, где R может быть произвольно большим. После выполнения настройки программы 10.3 на это приложение, мы будем называть ее многомерной быстрой сортировкой (multikey quicksort).

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

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

На первых порах не так то просто поверить, что этот метод работает; и в самом деле, он вообще не работает, если используемый метод сортировки неустойчив (см. определение 6.1). После того, как установлена важность свойства устойчивости, нетрудно дать формулировку доказательства того, что поразрядная сортировка LSD работает: мы знаем, что после упорядочения ключей по / замыкающим байтам (при сохранении устойчивости) любые два ключа в файле появляются в нужном порядке (в соответствии с просмотренными на текущий момент разрядами) либо благодаря тому, что первые из / замыкающих байтов отличны друг от друга, в подобном случае сортировка по этому байту расставила их в соответствующем порядке, или если первые из / замыкающих байтов совпадают, они уже упорядочены нужным образом в силу свойства устойчивости. Можно дать этому другую формулировку: если w-- / еще не просмотренных байтов какой- либо пары ключей идентичны, то любое различие между этими ключами определяется / байтами, которые уже просмотрены, и если эти ключи должным образом упорядочены, то они сохраняют этот порядок в силу свойства устойчивости. С другой стороны, если W-- / еще не просмотренных байтов различны, то те / байтов, которые уже просмотрены, не играют никакой роли, так что следующий проход должным образом упорядочит эту пару, учитывая различия в более значащих байтах.

Требование устойчивости означает, например, что метод разделения, использованный в двоичной быстрой сортировке, не может быть использован в двоичной версии рассматриваемого метода сортировки справа налево. С другой стороны, метод сортировки с подсчетом индексных ключей является устойчивым методом сортировки, что сразу же приводит нас к классическому и эффективному алгоритму. Программа 10.4 представляет собой реализацию этого метода. По-видимому, понадобится вспомогательный массив для целей распределения методы, которые используются б упражнениях 10.17 и 10.18, выполняющие распределение без использования дополнительной памяти, жертвуют устойчивостью в пользу отказа от дополнительного массива.

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

Программа 10.4. Метод поразрядной сортировки LSD

Данная программа реализует сортировку байтов в словах методом подсчета индексных ключей, продвигаясь слева направо. Реализация сортировки методом подсчета индексных ключей должна быть устойчивой. Если R равна 2 (благодаря чему bytesword и bitwordsидентичны), данная программа является прямой поразрядной сортировкой • • с проходом справа налево, с поразрядным просмотром (см. рис. 10.15).

template <classItem>

void radixLSD (Item a[], int 1, int r)

{ static Item aux[maxN];

for (int d = bytesword-1; d >= 0; d--)

{

int i, j, count[R+l] ;

for (j = 0; j < R; j++) countfj] = 0;

for (I = 1; I <= r ; I ++ )

count [digit (a [ I ] , d) + 1 ] ++;

for (j = 1; j < R; j ++ )

count [ j ] + = count [ j - 1 ] ;

for ( I = 1; I <= r; I ++)

aux [ count [ digit ( a [ I ] , d)]++] = a [ I ] ;

for ( I = 1; i <= r ; I ++ ) a [ I ] = aux [ I ]

Рисунок 15 иллюстрирует работу двоичной поразрядной сортировки LSD на условном примере упорядочения ключей, благодаря чему становится возможным сравнение с рис. 10.3. Для рассматриваемых 5-разрядных ключей полное упорядочение достигается за пять проходов по ключам справа налево. Сортировка записей с одноразрядным ключом сводится к разбиению файла таким образом, что все записи с ключом 0 следуют раньше всех записей с ключом 1. Как только что было показано, мы не можем пользоваться стратегией разбиения, которую мы в рассматривали в начале данной главы при обсуждении программы 10.1, несмотря на то, что она по всем признакам решает ту же проблему, в силу того, что она не устойчива. Имеет смысл рассмотреть поразрядную сортировку с основанием системы счисления, равным 2, поскольку во многих случаях ее удобно реализовать на высокопроизводительных машинах и в аппаратном обеспечении специального назначения (см. упражнение 10.38). В программах мы используем максимально возможное число разрядов с тем, чтобы уменьшить число проходов, которое ограничено только размерами массива рассматриваемых чисел (см. рис. 10.16).

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