Delphi-Help

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

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

Оцените материал
(3 голосов)


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

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

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.  
 
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). То есть, оценка времени работы сортировки слиянием меньше, чем у первых трех алгоритмов (я прошу прощения у тех, кто не понял мои рассуждения или не согласен с ними, — просто поверьте мне на слово). Перед тем как объяснить, чем этот метод лучше, рассмотрим еще один алгоритм.

Прочитано 10034 раз

Авторизация



Счетчики