(2.3Г

завершается, как только Будёт исчерпана одна из двух cepHi После этого остаток другой серии, который еше не исчерпа нужно переслать в выходную серию с помощью простого и пирования. Это осуществляется вызовом процедуры соруги Обе эти процедуры определены с помощью подчинение процедуры сору, которая пересылает элемент из файла в файл у и определяет, достигнут ли конец серии. Ее леп написать, используя операторы read и write. Для того чтоб; найти конец серии, нужно сохранять ключ последнего проч! тайного (переписанного) элемента для сравнения со следу!: щим. Это заглядывание вперед достигается использование буферной переменной файла х\. i

с

procedure copy(y t х,у: tape); j

yaxbuf: item; 1

begin readix, buf); write{y, buf); (2.3!

! if eof(x) thei eor := true else eor := buf.key > x\.key-end ) Ha этом построение процедуры сортировки естественнв слиянием закончено. К сожалению, как может заметить вй, мательный читатель, эта программа некорректна, посколЫ! в некоторых случаях она неправильно производит сор , ровку. Рассмотрим, например, такую последовательное входных данных:

3 2 5 11 7 13 19 17 23 31 29 37 43 41 47 59 57 61 71 6

Распределяя последовательные серии поочередно в фай*с

а и &, мы получим f

а==3 7 13 19 29 37 43 57 61 71 <

6 = 2 5 11. 17 23 31 41 47 59 67

Эти последовательности легко сливаются в одну серию, noj чего сортировка заканчивается. Хотя этот пример и не w

procedure mergerun; begin [слияние серий из a и b в с] repeat if af.key < b.key then begin copy(a,c);

ifeor then copyrm(b,c) end else

begin copyib.c);

if eor then cqpyrun(a,c)

end until eor

Процесс сравнения и^выбора по ключу при слиянии серц!

ошибочному поведению программы, он показывает, воД^ QCToe распределение серий в несколько файлов может f р результате меньшее число выходных серий, чем вход- Э-го происходит потому, что первый элемент (г--2)-й

гложет быть больше, чем последний элемент t-й серии, приведет к автоматическому слиянию двух серий в одну, хотя и предполагается, что процедура distribute посылает -w поровну в оба файла, действительные количества вы-*Р серий в й и & могут значительно различаться. Однако aiiia процедура будет только сливать пары серий и заканчи-VbCfl. как только будет прочитан файл Ь, теряя при этом статок одного из файлов. Рассмотрим такие исходные данные, которые сортируются (и усекаются) за два последовательных прохода:

Таблица 2.12. Неправильный результат работы программы сортировки слиянием

17 193 57 23 29 И 59 31 37 7 61 41 43 5 67 47 71 2 3 13 17 19 23 29 31 37 41 43 47 57 71 11 59 11 13 17 19 23 29 31 37 41 43 47 57 59 71

Эта ошибка типична для многих ситуаций. Она вы,звана тем, что упускается нз виду одно из возможных последствий, казалось бы, простой операции. Она также типична в том смысле, что сушествует несколько способов ее исправления и нужно выбрать один из них. Часто имеются две возможно-аи, различие между которыми носит принципиальный характер:

1- Мы видим, что операция распределения написана некорректно и не удовлетворяет требованию, чтобы число серий на двух лентах было одинаковым (или различалось не более чем на., 1). Придерживаемся принятой ранее схемы и соответствуюшим образом исправляем неправильную процедуру.

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

Вообще говоря, первый способ выглядит более понятным J Одежным, а также более честным; он в достаточной мере 5 °°ЗДен от непредусмотренных последствий и сложных по-og/bix эффектов. Следовательно, это тот путь, который

Но рекомендуется. У^нако надо указать, что бывают случай, когда не сле-пренебрегать второй возможностью. Поэтому ниже мы *ем на этом примере, как можно исправить ошибку,

program mergesort (input, output);

[Ъ-ленточная, 1-фазная сортировка естественным слиящ, type item = record key: integer \

[прочие поля] end ; tape == Шео1 item; var c: tape; .n: integer; buf: item;

procedure list (yatf: tape);

var x: item; begin reset(f);

while -neofif) do

begin read(f,x); write(output, x.key) end ; writeln

procedure naturalmerge;

yar I: integer; [число сливаемых серий]

eor: boolean; [индикатор конца серии}

a,b: tape; procedure cqpy(\at x,y: tape);

var buf: item; begin read(x, buf); write(y,buf);

if eof(x) then eor true else eor := buf.key > .vtice; end ;

procedure copyrUn (var x,y: tape); begin [перепись одной серии из x вУ\

repeat Сб>/>Х* >) til eor end ;

procedure distribute;

begin { 3 с e а.и b]

repeat copyrun (c,a);

if -10/(c) then copyrun (c,b)

until eof(c) end ;

procedure mergenin;, : begin [из a и b ec] repeat

if я-> < ftt-J *hen begin copj/ (a,c);

if eor then copyrun (b,c) end else begin copy (b,c);