|
begin A[k]:=A[i]; Inc(i); end
Else
begin A[k]:=A[j]; Inc(j); end;
end;
while i<=q do
// Цикл выполняется, пока левая половина не иссякла
// (правая половина исчерпана)
Begin
Inc(k); A[k]:=A[i]; Inc(i);
end;
while j<=r do
// Цикл выполняется, пока правая половина не иссякла
// (левая половина исчерпана)
Begin
Inc(k); A[k]:=A[j]; Inc(j);
end;
for i:=1 to n do
// Цикл выполняется для переброски массива из временного места в постоянное
A[i]:=A[i+nCurr];
end;
Ясно, что вызов процедур
СортировкаЛевойПоловины;
СортировкаПравойПоловины;
лучше заменить на рекурсивный вызов самой процедуры, которую мы обсуждаем. Тривиальным случаем следует считать тот, которому соответствует требование отсортировать набор из одного элемента массива.
Ниже приведен полный текст процедуры MergeSort – процедуры сортировки простым слиянием.
procedure MergeSort;
procedure Merge(p, q, r: integer);
Var
i, j, k: integer;
Begin
i:=p;
j:=q+1;
k:=n;
while (i<=q) and (j<=r) do
Begin
Inc(k);
IfA[i]<A[j] then
Begin
A[k]:=A[i];
Inc(i);
End
Else
Begin
A[k]:=A[j];
Inc(j);
end;
Inc(nM);
end;
while i<=q do
Begin
Inc(k);
A[k]:=A[i];
Inc(i);
end;
while j<=r do
Begin
Inc(k);
A[k]:=A[j];
Inc(j);
end;
k:=n;
for i:=p to r do
Begin
Inc(k);
A[i]:=A[k];
end;
end;
procedure MergeSortAux(p, r: integer);
Var
q: integer;
Begin
if p>=r then exit;
q:=(p+r) div 2;
MergeSortAux(p, q);
MergeSortAux(q+1, r);
Merge(p, q, r);
end;
Begin
MergeSortAux(1, nCurr);
end;
Сортировка прямым слиянием
Принцип сортировки поясняется следующим примером.
Пусть дан массив
В первой фазе сортировки массив делится пополам, половинки удобно считать расположенными одна над другой
Производится слияние (с сортировкой) одиночных чисел, расположенных одно над другим. Из этих пар вновь составляется один общий массив
который состоит из подряд идущих упорядоченных пар.
В второй фазе сортировки массив вновь делится пополам, половинки удобно считать расположенными одна над другой
Производится слияние (с сортировкой) теперь уже пар чисел, расположенных одна над другой. Из этих четверок вновь составляется один общий массив
который состоит из подряд идущих упорядоченных четверок.
Длина упорядоченных фрагментов растет «в геометрической прогрессии» и за короткое число фаз достигает длины всего массива.
Ниже приведен полный текст процедуры StraightMergeSort – процедуры сортировки прямым слиянием.
procedure StraightMergeSort;
Var
i,j,k,L,t,h,m,p,q,r:
integer;
bUp:
boolean;
Begin
nMove:=0;
nCompare:=0;
bUp:=true;
p:=1;
Repeat
h:=1;
m:=nCurr;
IfbUp then
begin i:=1; j:=nCurr; k:=nCurr+1; L:=2*nCurr; end
Else
begin k:=1; L:=nCurr; i:=nCurr+1; j:=2*nCurr; end;
Repeat
if m>=p then q:=p else q:=m;
m:=m-q;
if m>=p then r:=p else r:=m;
m:=m-r;
While(q<>0) and(r<>0) do
Begin
nCompare:=nCompare+1;
Дата добавления: 2015-04-26; просмотров: 13 | Поможем написать вашу работу | Нарушение авторских прав |
<== предыдущая лекция | | | следующая лекция ==> |
Сортировки слиянием | | | Теоретические основы моделирования производственных систем |