Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

IfA[i]<A[j] then

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 | Поможем написать вашу работу | Нарушение авторских прав

<== предыдущая лекция | следующая лекция ==>
Сортировки слиянием| Теоретические основы моделирования производственных систем

lektsii.net - Лекции.Нет - 2014-2024 год. (0.01 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав