Курсовая работа: Алгоритмы обработки больших массивов. Алгоритмы обработки данных

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 серий. Второй проход уменьшит это число до г/N² , третий — до r/N³ и т. д., после к проходов останется r/N^k серий. Поэтому общее число проходов, необходимых для сортировки n элементов с помощью N-путевого слияния, равно

k = [log_N n]

В программе сортируется массив файлов. Мы начнем с определений и к двум уже знакомым типам itemи sequenceдобавим тип

seqno = [l..N]

Теперь можно представить алгоритм.

MODULE BalancedMerge;

VAR1, j: seqno;

L: INTEGER; (* число распределяемых серий *).

t: ARRAY seqno OF seqno;