Алгоритм 4. Сортировка слиянием.

Previous  Top  Next

    
 

Алгоритм 4. Сортировка слиянием.

 

Эта сортировка использует следующую подзадачу: есть два отсортированных массива, нужно сделать (слить) из них один отсортированный. Алгоритм сортировки работает по такому принципу: разбить массив на две части, отсортировать каждую из них, а потом слить обе части в одну отсортированную. Корректность данного метода практически очевидна, поэтому перейдем к реализации.

Code:

Program SlivSort;

Var A,B : array[1..1000] of integer;

   N  : integer;

Procedure Sliv(p,q : integer); {процедура сливающая массивы}

Var r,i,j,k : integer;

Begin

r:=(p+q) div 2;

i:=p;

j:=r+1;

for k:=p to q do

if (i<=r) and ((j>q) or (a[i]<a[j])) then

begin

  b[k]:=a[i];

  i:=i+1;

end

else

begin

  b[k]:=a[j];

  j:=j+1;

end ;

for k:=p to q do

a[k]:=b[k];

End;

Procedure Sort(p,q : integer); {p,q — индексы начала и конца сортируемой части массива}

Begin

if p<q then {массив из одного элемента тривиально упорядочен}

begin

Sort(p,(p+q) div 2);

Sort((p+q) div 2 + 1,q);

Sliv(p,q);

end;

End;

Begin

{Определение размера массива A — N) и его заполнение}

{запуск сортирующей процедуры}

Sort(1,N);

{Вывод отсортированного массива A}

End.

 

 

 

Чтобы оценить время работы этого алгоритма, составим рекуррентное соотношение. Пускай T(n) время сортировки массива длины n, тогда для сортировки слиянием справедливо T(n)=2T(n/2)+O(n) (O(n) это время, необходимое на то, чтобы слить два массива). Распишем это соотношение:

 

T(n)=2T(n/2)+O(n)=4T(n/4)+2O(n/2)+O(n)=4T(n/4)+2O(n)= … = 2kT(1)+kO(n)

 

Осталось оценить k. Мы знаем, что 2k=n, а значит k=log2n. Уравнение примет вид T(n)=nT(1)+ log2nO(n). Так как T(1) константа, то T(n)=O(n)+log2nO(n)=O(nlog2n). То есть, оценка времени работы сортировки слиянием меньше, чем у первых трех алгоритмов (я прошу прощения у тех, кто не понял мои рассуждения или не согласен с ними, просто поверьте мне на слово). Перед тем как объяснить, чем этот метод лучше, рассмотрим еще один алгоритм.

©Drkb::04146