Если объединить два концептуально различных массива в один-единственный, но двойного размера, то программа еще более упрощается. В этом случае данные представляются так:
a: ARRAY[1..2*n] OFitem
Начальное значение р равно 1, и перед каждым последующим проходом она удваивается. Для простоты мы предполагаем, что всегда n равно степени двойки. Таким образом, первая версия программы сортировки с помощью простого слияния имеет такой вид
PROCEDURE MergeSort:
VAR i, j, k, L: index; up: BOOLEAN; p: INTEGER;
BEGIN up : = TRUE; p : = 1;
REPEAT инициациииндексов;
IFupTHEN i:=l; j:=n; k:=n+1;L:=2*n
ELSE k:= l;L:= n; i := n+1; j := 2*n
END;
слияние р-наборов из i- и j-входов в k- и L-выходы;
Up:= ~up; p:=2*p
UNTIL p = n
ENDMergeSort
Следующий этап — уточнение операторов, выделенных курсивом. Ясно, что процесс слияния n элементов сам представляет собой последовательность слияний последовательностей, т. е. р-наборов. После каждого такого частичного слияния выход переключается с нижнего на верхний конец выходного массива и наоборот, что гарантирует одинаковое распределение в обоих направлениях. Если сливаемые элементы направляются в левый конец выходного массива, то направление задается индексом к и после пересылки очередного элемента он увеличивается на единицу. Если же элементы направляются в правый конец, то направление задается индексом L и он каждый раз уменьшается. Для упрощения фактического оператора слияния будем считать, что направление всегда задается индексом к, но после слияния р-набора будем менять местами значения к и L, приращение же всегда обозначается через h, имеющее значение либо 1, либо —1.
Поскольку на каждом проходе р удваивается и сортировка заканчивается при р> n, то всего требуется [logn] проходов. На каждом проходе по определению копируются по одному разу все n элементов
Алгоритм сортировки слиянием выдерживает сравнение даже с усовершенствованными методами. Однако, хотя здесь относительно высоки затраты на работу с индексами, решающее значение играет необходимость работать с памятью размером 2n. Поэтому сортировка слиянием для массивов, т. е. для данных, размещаемых в оперативной памяти, используется редко.
Естественное слияние
В случае прямого слияния мы не получаем никакого преимущества, если данные в начале уже частично упорядочены. Размер сливаемых на к-м проходе подпоследовательностей меньше или равен 2к и не зависит от существования более длинных уже упорядоченных подпоследовательностей, которые можно было бы просто объединить. Фактически любые две упорядоченные подпоследовательности длиной m иn можно сразу сливать в одну последовательность из m + n элементов. Сортировка, при которой всегда сливаются две самые длинные из возможных подпоследовательностей, называется естественным слиянием.
Упорядоченные подпоследовательности часто называют строками. Однако так как слово «строка» еще чаще употребляется для названия последовательности символов, то мы для упорядоченных подпоследовательностей будем использовать термин «серия». Поэтому в сортировке естественным слиянием объединяются (максимальные) серии, а не последовательности фиксированной (заранее) длины. Если сливаются две последовательности, каждая из n серий, то результирующая содержит опять ровно n серий. Следовательно, при каждом проходе общее число серии уменьшается вдвое и общее число пересылок в самом плохом случае равно n*|logn|, а в среднем даже меньше. Ожидаемое же число сравнений, однако, значительно больше, поскольку кроме сравнений, необходимых для отбора элементов при слиянии, нужны еще дополнительные — между последовательными элементами каждого файла, чтобы определить конец серии.
Следующим нашим упражнением будет создание алгоритма естественного слияния с помощью того же приема пошагового уточнения, который применялся при объяснении алгоритма прямого слияния.
VARL: INTEGER; а, b, с: Sequence
REPEAT Reset(a); Reset(b); Reset(c):
Распределение; (*с распределяется в а и b*)
Reset(a); Reset(b); Reset(c);
L: = 0; слияние (*а и b сливаются в с *)
UNTILL = 1
Две фазы явно выделяются как два различных оператора. Теперь их надо уточнить, т. е. переписать с большей детализацией. Уточненное описание распределения (distribute) приведены ниже .
RЕРЕАТ copyrun(c, a);
IF~c.eof THENcopyrun(c,b)END
UNTIL с.eof
REPEAT mergerun; L: = L+1
UNTIL b.eof;
IF ~a.eof THEN copyrun(a, c); L := L+l END
Такой метод распределения приводит предположительно к следующему результату: либо в а и b будет поровну серий, либо в а будет на одну больше. Поскольку соответствующие пары серий сливаются в одну, то b а может оказаться еще одна лишняя серия, ее нужно просто скопировать.
Вместо того чтобы программировать явно этот механизм в нашей программе, мы предпочитаем определить еще один уровень абстракции. Это будет новый модуль с именем Sequences, для пользователя он заменит модуль FileSystem. Кроме того, мы определяем соответственно и новый тип для последовательности, но он будет ссылаться на Sequenceиз FileSystem. В этом новом типе будет фиксироваться не только конец последовательности, но и конец серии и, конечно же, первый элемент оставшейся части последовательности. Новый тип и связанные с ним операции задаются таким модулем определений:
DEFINITION MODULE Sequences;
IMPORT FileSystem;
TYPE item = INTEGER;
Sequence = RECORD first: item;
eor.eof: BOOLEAN;
f: FileSystem.Sequence
END;
PROCEDURE OpenSeq(VARs: Sequence);
PROCEDURE OpenRandomSeq(VARs: Sequence; length, seed: INTEGER); PROCEDURE StartRead(VARs: Sequence);
PROCEDURE StartWrite(VAR s: Sequence);
PROCEDURE copy(VAR x, y: Sequence);
PROCEDURE CloseSeq(VAR s: Sequence);
PROCEDURE ListSeq(VAR s: Sequence);
ENDSequences.
Процесс сравнения и выбора ключей при слиянии серий заканчивается, как только исчерпается одна из двух серий. После этого оставшаяся неисчерпанной серия просто передается в результирующую серию, точнее копируется ее «хвост».
Сбалансированное многопутевое слияние
Затраты на любую последовательную сортировку пропорциональны числу требуемых проходов, так как по определению при каждом из проходов копируются все данные. Один из способов сократить это число — распределять серии в более чем две последовательности. Слияние r серий поровну распределенных в N последовательностей даст в результате r/N серий. Второй проход уменьшит это число до г/N2, третий — до r/N3 и т. д., после к проходов останется r/Nkсерий. Поэтому общее число проходов, необходимых для сортировки n элементов с помощью N-путевого слияния, равно
k = [logNn]
В программе сортируется массив файлов. Мы начнем с определений и к двум уже знакомым типам itemи sequenceдобавим тип
seqno = [l..N]
Теперь можно представить алгоритм.
MODULE BalancedMerge;
VAR1, j: seqno;
L: INTEGER; (* число распределяемых серий *).
t: ARRAY seqno OF seqno;
BEGIN (* распределение начальных серий в- t[l] ...t[Nh] *)
j:=Nh;L:=0;
REPEAT
IF j < Nh THEN x := j+l ELSE j: = 1 END;
копирование одной серии из f0 в последовательность J;
L:=L+1
UNTIL fo.eof;
FORi:=l TO N DO t[i]:=I END;
REPEAT (* слияние из t[l]...t[nh] в t[nh+l]...i[n]*)
установка входных последовательностей;
L: = 0;
j:=Nh+l; (*j -индекс выходной последовательности*)
REPEATL:=L+1;
слияние а серий с входов bi(j);
IF j < N THEN j : = j+l ELSE j := Nh+I END
UNTILвсе входы исчерпаны
переключение последовательностей
UNT1LL = 1
(• отсортированная последовательность в t [1 ] *)
ENDBalancedMerge,
Многофазная сортировка
Мы уже познакомились с необходимыми приемами и в достаточной мере готовы к исследованиям и программированию, связанным с новыми, более эффективными, чем сбалансированная сортировка, алгоритмами. В основе нашего очередного усовершенствования лежит отказ от жесткого понятия прохода и переход к более изощренному использованию последовательностей. Мы больше не будем считать, что есть N/2 входов и столько же выходов и они меняются местами после каждого отдельного прохода. Более того, уже само понятие прохода делается расплывчатым. Новый метод был изобретен Р. Гилстэдом [2.3] и называется многофазной сортировкой (PolyphaseSort).
Многофазная сортировка более эффективна, чем сбалансированная, поскольку она имеет дело с N—1-путевым слиянием, а не с N/2-путевым, если она начинается с N последовательностей. Ведь число необходимых проходов приблизительно равно logN *n, где n — число сортируемых элементов, а N — степень операции слияния, — это и определяет значительное преимущество нового метода.
Фактически операция слияния почти идентична той же операции в сортировке с помощью N-путевого слияния, разница только в том, что здесь алгоритм исключения последовательности несколько проще.
Глава 2. Практические задачи по алгоритмам обработки данных
2.1 Решение задачи о пяти ферзях
Постановка задачи: Найти расстановку пяти ферзей, при которой каждое поле шахматной доски будет находится под ударом хотя одного из них.
Задача о пяти ферзях — хорошо известный пример использования метода проб и ошибок и алгоритмов с возвратом. Для подобных задач характерно отсутствие аналитического решения. Вместо этого они требуют большого объема изнурительных вычислений, терпения и аккуратности. Поэтому такие задачи стали почти исключительно прерогативой вычислительных машин, которые обладают этими свойствами в гораздо большей степени, чем люди, даже гениальные.
Поскольку мы знаем, что по шахматным правилам ферзь бьет все фигуры, расположенные на той же горизонтали, вертикали или диагонали доски, то мы заключаем, что каждая вертикаль может содержать одного и только одного ферзя.
Осталось решить, как представить расположение пяти ферзей на доске. Очевидно, что доску можно было бы вновь изобразить в виде квадратной матрицы, но после некоторого размышления мы обнаруживаем, что такое представление значительно усложнило бы проверку безопасности позиции. Это крайне нежелательно, поскольку такая операция выполняется наиболее часто. Поэтому нужно выбрать представление, которое насколько возможно упростит эту проверку. Лучше всего сделать наиболее доступной ту информацию, которая действительно важна и чаще всего используется. В нашем случае это не расположение ферзей, а информация о том, помещен ли ферзь на данной горизонтали или диагонали.