regram distributeifOJUoutpui);

Тачальное распределение серий с помощью пирамидальной сортировки]

const т 30; mh = 15; [размер пирамиды] Zpeitem = record

key: integer end ; tape file of item;

-fndex = 0., да-;-------

var : itdx; /0,/l: tape;

count: integer; [счетчик серий] ft: array [1.. m] of item; [пирамида]

procedure selecttape;

begin count := count + I;

[фиктивная процедура; подсчитывает число распределенных

серий] еой [selecttape] ;

jfxoccdvte sift(l,r: index); label 13;

var integer: x: item; begin / /; / := 2*i; x := h[i\; while 7 < r do

tbegin if / < r then if li[f\ .key > hlJ+1] .key then j :== J+l; ; if x .key < h[f\ .key then goto 13; h[q h[j]; i := j; j := 2*i

end ;

13: f,[i] : X end ;

begin [формирование начальных серий с помощью пирамидального сортировки] count := 0; reset(fO); rewrite(fl); selecttape;

[этап 1: заполнение верхней части пирамиды h] 1:т;

repeat read(fO, h[l]); I := /-1 until I = mh;

[этап 2: заполнение нижней части пирамиды h} repeat readifО, li[l]); sift{l,m); / := /-1 until / = 0;

{man 3: пропуск серий через пирамиду]

I := т;

while -ieof(/0) do begin writeif I,

if Л[1] .key < /Ot .Arej; then

begin {новая запись принадлежит той же серии] readifO, Л[1]); sifiihl);

end else

begin {новая запись принадлежит следующей серии] Л11] := ЛИ; siftiU-l); readifO, h[lj); if I <, mh then sifiihrn); I :== if / == 0 then

begin {пирамида заполнена; начать новую серию]

/ т; splpr.ttnpp.;

end I

end end ;

{этап 4: сброс нижней части пирамиды]

г := т;

repeat wn7e(/l, А[1]);

Л[1] := ад; siftiU-l); I

ад := Цг]; г := r-l;

if / те/г ihensiftil,r); / := /-1 until / = 0;

{этап 5: сброс верхней части, пирамиды; формирование последней серии]

selecttape; while г > О do begin writeif l,li[lj);

Ml] := h[r]; siftil,r); r := r-l end ;

writeln {count) end .

Программа 2.17. Распределение начальных серий с помощыо пирамиды.

Оценку свойств многофазной сортировки можно получи гь из табл. 2.15, определив максимальное число начальных серий, которые можно отсортировать за данное количество частичных проходов (уровней) при заданном числе п лент. Например, при п = 6 лентах и пирамиде размером m = 100 файл, содержащий до 165680100 начальных серий, можно отсортировать за 20 частичных проходов. Это - отличные характеристики.

рассматривая программу, представляющую собой комби- ю многофазной и пирамидальной сортировки, нельзя че азиться ее сложности. Ведь она выполняет ту же самую, гКО определимую задачу переупорядочения множества эле- ятов, что и любая из коротких программ, основанных на *остых методах сортировки массивов. Из всего сказанного Р^этой главе можно сделать следующие выводы:

1 Д1ежду алгоритмом и структурой данных существует тес- рая связь; структура данных оказывает большое влияние

на вид программы-

2 При помощи усложнения программы можно значительно повысить,-° эффективность, даже когда структура данных, с которо) 1 работает, плохо соответствует поставленной задаче. V ч

\ УПРАЖНЕНИЯ

2.1. Какие из алгоритмов, представленных программами 2.1-2.6, 2.8, 2.10 и 2.13, являются методами устойчивой сортировки?

2.2. Будет ли программа 2.2 работать правильно, если в условии окончания цикла заменить I г на I <Z г? Будет ли она по-прежиему правильной, если операторы г: = т - 1 и 1:= т-\-1 упростить до г:=т и 1:=т? Если нет, найдите множества значений ai,..a , при которых измененная программа будет работать неправильно.

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

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

x.key а [i].key

из цикла с предусловием?

2.5. Рассмотрите следующую очевидную версию программы разделения

2.9:

/ :=!;/:= я;

X := й[(й+1) div 2].key;

repeat

while aii].key < л: do r := /-f 1; whHe X < aljlkey uoj :=/-1; w := ali]; ali] := [/]; [/] := w until >y

Найдите множества значений ai... an, для которых эта версия работает неправильно.

Напишите программу, которая комбинирует алгоритмы быстрой сортировки и сортировки методом пузырька следующим образом: используется быстрая сортировка для получении (неотсортированных)