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

Начальное значение р равно 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, то всего требуется [logⁿ ] проходов. На каждом проходе по определению копируются по одному разу все 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