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

Рисунок 7.12 служит иллюстрацией работы алгоритма разбиения на три части на примере учебного файла, а профамма 7,5 содержит реализацию бысфой сортировки, в основу которой положен этот метод. Рассматриваемая реализация требует добавления двух операторов if в цикл обмена и двух циклов for с тем, чтобы процедура разделения завершалась помещением ключей, равных разделяющему элементу, в окончательные позиции. По-видимому, на это потребуется меньше программного кода, чем в случае других альтернатив разделения файла на три части. И что более важно, этот метод не только исключительно эффективно решает проблему дублированных ключей, но и привносит минимально возможный объем непроизводительных затрат в случае, когда в исходном файле вообще нет дублированных ключей.

Программа 7.5. Быарая сортировка с разделением на три части

А в А В

ACACABRABC D©

ABC С В А

D С D С

В А А В В А А В

С R D С D R С С

С В А А В С В А А В

С D R С С R О С С С

СВААВААА B®R D С С R В В А А В А А A©C<8)©D R R

РИСУНОК 7.12. РАЗДЕЛЕНИЕ НА ТРИ ЧАСТИ

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

В основу программы положено разделение массива на три части: на элементы, меньшие разделяющего элемента (в позиции а[1],..., a[j]), элементы, равные разделяющему элементу (в позиции a[j+1],..., а[1-1]), и элементы большие разделяющего элемента (в позиции a[i],..., а[г]). После этого сортировка завершается двумя рекурсивными вызовами.

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

да указатели просмотра перестают изменяться и выполняется обмен значениями I и j, она проверяет каждый из этих элементов на предмет равенства разделяющему элементу. Если элемент, который сейчас находится слева, равен разделяющему элементу, то при помощи операции обмена он помещается в левую часть массива; если элемент, который сейчас находится справа, равен разделяющему элементу, то в результате операции обмена он помещается в правую часть массива.

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

template <class Item>

int operator=: (const Item SA, const Item SB)

{ return 11ess(A, B) fifi !less(B, A); } template <class Item>

void quicksort (Item a[] , int 1, int r) { int k; Item v = a[r]; if (r <= 1) return;

int i = 1-1, j = r, p = 1-1, q = r; for (;;) {

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

while (V < a[~j]) if (j == 1) break; if (i >= j) break; exch(a[i],a[j]);

if (a[i] == V) { P++; exch(a[p] ,a[i]) ; } if (V == a[j]) { q-; exch(a[q] ,a [ j]) ; }

exch (a [i], a[r]); j = i-1; i = i+1;

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

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

quicksort(a, 1, j) ;

quicksort(a, i, r) ;

Упражнения

[> 7.34. Дайте объяснения тому, что происходит, когда профамма 7.5 выполняется на файле с произвольной организацией (/) с двумя различными значениями ключей и ( ) с тремя различными значениями ключей.

7.35. Изменить программу 7.1 таким образом, чтобы она выполняла команду return, если все ключи в подфайле одинаковы. Сравните эффективность полученной программы с эффективностью программы 7.1 на больших файлах с произвольной организацией с ключами, принимающими / различных значений при /= 2, 5 и 10.

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

7.37. Доказать, что время выполнения программы из упражнения 7.37 пропорционально квадрату длины файлов для всех файлов с 0(1) различных значений ключей.

7.38. Написать программу, определяющую количество различных ключей, которые встречаются в файле. Воспользуйтесь полученной программой для подсчета числа различных ключей в файле с произвольной организацией, состоящего из Л целых чисел, принимающих значения в диапазоне от О до М- 1 для М = 10, 100 и 1000 и для yV= 10 10 10 и 10

7.7 Строки и векторы

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

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

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

Процедура разделения файла на три части, которая рассматривалась в разделе 7.6, представляет собой элегантный способ извлечь пользу из отмеченного выше факта. На каждой стадии процесса разделения проверяется только один символ (скажем, символ в позиции d), предполагая; что ключи, занимающие позиции от О до d-1 и подлежащие сортировке, совпадают. Мы выполняем разделение на три части, помещая те ключи, d-й символ которых меньше d-ro символа разделяющего элемента, слева, те ключи, d-й символ которых равен d-му символу разделяющего элемента, в середине, а те ключи, d-й символ которых больше d-ro символа разделяющего элемента, справа. Далее мы выполняем обычные действия за исключением того, что мы сортируем средний подфайл, начиная с d+1-го символа. Нетрудно видеть, что этот метод обеспечивает корректную сортировку и к тому же обладает исоючительно высокой эффективностью (см. табл. 7.2). В данном случае мы получаем убедительный пример неограниченных возможностей рекурсивного мышления (и программирования).

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