О 8.4. Верно ли утверждение, что программа 8.1, вызванная так, как показано в упражнении 8.3, работает правильно тогда и только тогда, когда оба входных подмассива уже отсортированы? Докажите правильность выводов или представьте контрпример.

8.2. Абстрактное обменное слияние

Хотя реализация слияния, по-видимому, требует дополнительного пространства, мы все еще считаем абстракцию обменного слияния полезной при реализации методов сортировки, которые здесь изучаются. В нашей следующей реализации слияния мы сделаем акцент на этом моменте за счет использования интерфейса merge(a, 1, m, г), тем самым показывая, что подпрофамма помещает результат слияния а[1],.мЯ[1п] и a[in+l],...,a[r] в объединенный упорядоченный файл а[1],..., а[г]. Можно было бы реализовать эту программу слияния, сначала скопировав абсолютно все во вспомогательный файл с последующим применением базового метода, использованного в программе 8.1, однако пока мы не будем делать этого, а сначала внесем одно усовершенствование в данный подход. И хотя дополнительное пространство памяти для вспомогательного массива, по-видимому, на практике связано с определенной ценой, в разделе 8.4 мы рассмотрим дальнейшие улучшения, которые позволят избежать дополнительных затрат времени, требуемого на копирование массива.

Вторая, заслуживающая внимания, основная характеристика базового слияния заключается в том, что внутренний цикл содержит две проверки с целью определить, достигнут ли конец хотя бы одного из двух массивов. Разумеется, чаще условие этой проверки не подтверждаются, и складывается исключительно благоприятная ситуация для использования служебных ключей, позволяющих отказаться от такого рода проверок. Иначе говоря, если элементы со значениями ключей, большими, чем значения всех других ключей, добавляются в конец массива а и массива aux, от этих проверок можно отказаться в силу того, что если массив а (Ь) будет исчерпан, служебный ключ позволяет перейти в режим выборки следующих элементов только из массива b (а) и помещать их в массив с вплоть до окончания операции слияния.

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

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

Программа 8.2. Абарактное обменное слияние

Данная программа выполняет слияние двух файлов без использования служебных меток, путем копирования второго массива в массив aux в обратном порядке, когда сразу за концом первого массива следует конец второго (т.е., устанавливая на aux битонный (bitonic) порядок). Первый цикл for перемещает первый массив, после чего i указывает на I, что означает готовность начинать слияние. Второй цикл for перемещает второй массив, после чего j указывает на г. Затем в процессе слияния (третий цикл for) наибольший элемент служит служебной меткой независимо от того, в каком файле он находится. Внутренний цикл этой программы достаточно короткий (перенос в aux, сравнение, перенос обратно в а, увеличение значений i или j на единицу, увеличение на единицу и проверка значения к).

template <class Item>

void merge(Item a[] , int 1, int m, int r) { int i, j;

static Item aux[maxN];

for (i = m+1; i > 1; i--) aux[i-l] = a[i-l]; for (j = m; j < r; j++) aux[r+m-j] = a[j+l]; for (int к = 1; к <= г; k++) if (aux[j] < aux[i])

a[k] = aux[j-]; else a[k] = aux[i++] ;

a r s t g 1 n

РИСУНОК 8.1. СЛИЯНИЕ БЕЗ ИСПОЛЬЗОВАНИЯ СЛУЖЕБНЫХ МЕТОК.

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

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

Одно из важных свойств программы 8.1 заключается в том, что реализуемое ею слияние устойчиво: она сохраняет Относительный порядок элементов с одинаковыми ключами. Эту характеристику нетрудно проверить, и часто имеет смысл убедиться в том, что устойчивость сохраняется при реализации абстрактного обменного слияния, поскольку устойчивое слияние немедленно приводит к устойчивым методам сортировки, как будет показано в разделе 8.3. Не всегда просто сохранить свойство устойчивости: например, программа 8.1 не обеспечивает устойчивости (см. упражнение 8.6). Это обстоятельство еще больше усложняет проблему разработки истинного алгоритма обменного слияния.

Упражнения

> 8.5. В стиле примера, представленного на диаграмме 8.1, показать, как выполняется слияние ключей AEQSUYEINOSTc использованием программы 8.1.

о 8.6. Объяснить, почему программа 8.2 не является устойчивой, и разработать устойчивую версию этой программы.

8.7. Что получится, если программу 8.2 применить к ключам EASYQUEST I О N?

о 8.8. Верно ли, что профамма 8.2 выполняет правильный вывод тогда и только тогда, когда оба входных подмассива представлены в порядке, установленном сортировкой? Приведите аргументы в пользу своего ответа либо представьте контрпример.

8.3. Нисходящая сортировка слиянием

Имея в своем распоряжении процедуру слияния, нетрудно воспользоваться ею в качестве основы для рекурсивной процедуры сортировки. Чтобы отсортировать заданный файл, мы делим его на две части, выполняем рекурсивную сортировку обеих частей, после чего производим их слияние. Реализация этого алгоритма представлена в профамме 8.3; пример иллюстрируется на рис. 8.2. Как отмечалось в главе 5, этот алгоритм является одним из широко известных примеров использования принципа разделяй и властвуй разработке эффективных алгоритмов.

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

Сортировка слиянием играет важную роль благодаря простоте и оптимальности заложенного в нее ме-

ASORT I NGEXAMPLE А S

О я А О я S

G N G I N Т А G I N О я S Т

А Е М X

L Р Е L Р А Е Е L М Р X AAEEG I LMNO PR S Т X

РИСУНОК 8.2. ПРИМЕР НИСХОДЯЩЕЙ СОРТИРОВКИ СЛИЯНИЕМ

Каждая строка показывает результат вызова функции mergesort в процессе нисходящей сортировки слиянием. Сначала выполняется слияние А и S, чтобы получить AS, затем слияние Ои R, чтобы получить OR, а затем слияние OR и AS, чтобы получить AORS. Далее осуществляется слияние IT и GN, чтобы получить GINT, затем этот результат сливается с AORS и получается AGINORST и т.д. При помощи этого метода производится рекурсивное построение отсортированных файлов из отсортированных файлов меньших размеров.