Procedure Distribute

Type

TElem=integer;

TFile=file of TElem;

TSequence=class

Private

F: TFile;

FElem: TElem;

FEof: Boolean; //все ли записали

FCount: integer; //сколько осталось

FFileName: string;

Constructor Create(AFileName: string)

Begin

FFileName: =AFileName;

AssignFile(F, FFileName);

FEof: =true;

FCount: =0;

End;

Function SizeOf: integer;

Begin

Reset(f);

Result: =system.FileSize(F);

CloseFile(f);

End;

Procedure StartRead(len: integer);

Begin

Reset(f);

FEof: =system.Eof(f);

FCount: =len;

If not FEof then read (f, FElem);

End;

Procedure StartWrite

Rewrite (f);

Procedure CloseFile

System.CloseFile(f);

Procedure StartRun(len: integer);

FCount: =len;

Procedure Copy (y: TSequence);

Begin

Write(y.F, FElem);

FEof: =system.eof(f);

Dec(FCount)

If not FEof then read(f, FElem);

End;

Procedure CopyRun (y: TSequence);

Repeat Copy(y) until eor;

Function GetEor: Boolean;

Result: =Eof or (FCount=0)

Procedure Distribute

(f0, f1, f2: Tsequance; len: integer);

Begin

Fo.StertRead(len);

F1\f2.StartWrite;

While not f0 eof do begin

Fo.CopyRun(f1); f0.StartRun(len);

If not f0 eof then begin

Fo.copyRun(f2); fo.StartRun(len); end; end

F0\f1\f2. CloseFile;

End;

Procedure Merge (f0, f1, f2: TSequence; len: int);

Begin

F0.StartWrite;

F1\f2. StartRead(len);

While (not f1.eof) and (not f2.eof) do begin

F1\f2. StartRun(len);

While (not f1.eof)and(not f2.eor) do

If f1.elem< f2.elem then f1.copy(f0)

Else f2.copy(f0)

If not f1.eor then f1.CopyRun(f0)

Else f2.copyRun(f0); end;

If not f1.eof then begin

F1.StartRun(len); f2.CopyRun(f0); end;

F1\f2\f0. CloseFile;

End;

Procedure Sort (FileName: string);

Var f0, f1, f2: TSequance; n, len: integer;

Begin

F0.TSequance.Create(filename)

N: =f0.SizeOf;

If N> 1 then begin

F1: =TSequance.Create(‘a.tmp’);

F2: = -\\- (‘b.tmp’);

Len: =1;

Repeat

Distribute(f0, f1, f2, len);

Merge(f0, f1, f2, len);

Len: =len*2;

Until len> =N

F1.Erase; f1.Destroy;

--\\--- (f2); end;

F0.Destroy;

End;

Однофазное

Procedure MergeRun (f1, f2, f3: TSecuance;

Len: integer);

Begin

F1\f2. StartRun(len);

While (not f1.eor)and(not f2.eor) do

If f1.Elem< =f2.Elem then f1.copy(f3);

Else f2.copy (f3);

If not f1.eor then f1.copyrun(f3)

Else f2.copyrun(f3);

End;

Procedure Merge (f1, f2, f3, f4: TSequance;

Var len: integer);

Begin

F1\f2. startRead(len);

F3\f4.startWrite;

While(not f1.eof)or(not f2.eof) do begin

MergeRun(f1, f2, f3, len);

If not (f1.eof)or(not f2.eof) then

MergeRun(f1, f2, f3, len); end;

F1\f2\f3\f4. CloseFile;

Len: =len*2;

End;

Procedure Sort (filename: string);

Var f0, f1, f2, f3, f4: TSequance;

N, len: ineteger; ok: Boolean;

Begin

F0: =TSequance.Create(filename);

N: =f0.SizeOf;

If N> 1 then begin

F1\f2\f3\f4: = TSequance.Create(имя);

Len: =1; ok: =true;

Distribute (f0, f1, f2, len);

Repeat

Merge(f1, f2, f3, f4, len);

Ok: =not ok;

If len< N then begin

Merge(f3, f4, f1, f2, len);

Ok: =not ok; end;

Until len> =N

If ok then begin

F3.rename(filename); f3.erase; end;

Else begin

F3.rename(filename);

F1.erase; end;

F1\f2\f3\f4.free; end;

Fo.free;

End;

Естественное слияние

Сортировка, при которой всегда сливаются две самые длинные из возможных серий, называется естественным слиянием. В сортировке естественным слиянием объединяются серии максимальной, а не заранее фиксированной длины. Признаком конца серии в этом случае является результат сравнения двух соседних элементов, если они не упорядочены, то серия закончилась. В каждом проходе число серий уменьшается в N раз (если количество серий во вспомогательных файлах одинаково), а общее число пересылок не более, чем n × [log n ]. Ожидаемое число сравнений значительно больше, поскольку кроме сравнений, необходимых для слияния, требуются дополнительные сравнения для определения конца серии.

Так же как и простое слияние, сортировка естественным слиянием может быть двухпутевой или многопутевой, двухфазной или однофазной.

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

Естественное слияние, у которого после фазы распределения количество серий во вспомогательных файлах отличается друг от друга не более чем на единицу, называется сбалансированным, в противном случае речь идет о несбалансированном слиянии. Чтобы в сбалансированном слиянии серии распределялись корректно, необходимо во время записи очередной серии в файл выполнять следующую проверку: если серия является продолжением предыдущей, то записать в этот файл не одну, а две серии.

Не сбалансированное:

По сравнению с простым, меняются следующие процедуры:

Двухпутевое:

Procedure StartRead;

Begin

Reset(f);

FEof: =system.eof(f);

Feor: =system.eor;

If not FEof then read(f, fElem);

End;