15. Сортировка слиянием и ее реализация с помощью рекурсии. Временная сложность алгоритма.

 

Применим к алгоритму сортировки включением принцип “балансировки”: вместо разделения элементов массива на один и остальные (сортировка включением) или на h-серии (сортровка Шелла) разделим массив на две примерно равные части, рекурсивно упорядочим каждую из них, после чего эти упорядоченные части сольем. Под слиянием понимают объединение двух уже упорядоченных последовательностей в одну упорядоченную последовательность.

            Рассмотрим подробнее подпрограмму Confluence, осуществляющую процедуру слияния. Сначала элементы двух входных упорядоченных последовательностей помещаются в стеки S1 и S2 (по одному стеку на каждую последовательность). Третий стек S3 служит для формирования упорядоченной выходной последовательности. Первоначально он пуст. Затем осуществляется сравнение верхних элементов в стеках S1 и S2. Наибольший из двух сравниваемых элементов переносится из своего стека в S3. Сравнения осуществляются до тех пор, пока один из стеков S1, S2 (или оба сразу) не опустеет. Если опустел один из этих стеков, то оставшиеся элементы из второго просто “перегружаются” в S3.

            Очевидно, что процедура слияния требует не более чем n1+n2-1 сравнений, где n1и n2 - это число элементов во входных последовательностях.

************* P1={1,3,7}, P2={1,8} *****************

            Так как исходная задача размера n была разбита на две подзадачи n/2, после чего потребовалось n1+n2-1=n-1 сравнений, чтобы произвести слияние, то максимальная сложность этого алгоритма может быть описана рекуррентным уравнением:

Воспользовавшись результатами пр-ра 4.2 главы II, найдем порядок решения этого уравнения: . Таким образом, для больших n сбалансированность задачи дала значительную выгоду.

            На рис. 3.4 представлена программа, реализующая сортировку слиянием. Заметим, что в процессе работы этой программы приходится часто “перекладывать” элементы массива из одного стека в другой. Поэтому лучше оперировать не с самими элементами, а со ссылками на них.  Процедуры AddFILO и DelFILO совпадают с процедурами, описанными в § 2.1 главы I, с той лишь разницей, что переменная ch имеет тип pointer.

 

Program Confluence_Sr;

uses crt;

const n0=500;

type  pointer=^node; node=record key:integer; info:string[8] end;

         ptr=^element; element=record d:pointer; p:ptr end;

var   n:integer; pr:array[1..n0] of pointer; back,k:ptr;

procedure Confluence(top1,top2:ptr; var top_back:ptr);

  var top_med:ptr;

  begin

    top_med:=nil;

    while (top1<>nil) or (top2<>nil) do

     begin

        if top1=nil then   begin AddFILO(top_med,top2^.d); DelFILO(top2) end

        else

          if top2=nil then begin AddFILO(top_med,top1^.d); DelFILO(top1) end

          else

             if (top2^.d^.key>top1^.d^.key) then

                 begin AddFILO(top_med,top2^.d); DelFILO(top2) end

             else

                 begin AddFILO(top_med,top1^.d); DelFILO(top1) end

     end;

     while top_med<>nil do

      begin AddFILO(top_back,top_med^.d); DelFILO(top_med) end;

 end; {*Confluence*}

 

 procedure ConfluenceSort(first,last:integer; var back:ptr);

  var porog,m,i:integer; s1,s2:ptr;

  begin {*ConfluenceSort*}

    porog:=last-first; back:=nil; s1:=nil; s2:=nil;

    if porog=0 then AddFILO(back,pr[first])

    else

      begin

       m:=(first+last) div 2;

       ConfluenceSort(first,m,s1); ConfluenceSort(m+1,last,s2); Confluence(s1,s2,back);

       if porog=n-1 then

          for i:=1 to n do begin pr[n-i+1]:=back^.d; DelFILO(back) end;

      end;

  end; {ConfluenceSort}

 

var s:string[6]; i:integer;

BEGIN

     clrscr; write('Enter element"s number (n<=500) '); readln(n); Randomize;

     for i:=1 to n do

         begin

           new(pr[i]); pr[i]^.key:=Random(99)+1;

           str(pr[i]^.key,s); pr[i]^.info:='!-'+s+'-!'

         end;

     writeln('A before Sort'); for i:=1 to n do write(pr[i]^.key,pr[i]^.info,' '); writeln;

     ConfluenceSort(1,n,back);

     writeln('A after Sort'); for i:=1 to n do write(pr[i]^.key,pr[i]^.info,' '); writeln;

     writeln('Press "Enter" to end');

     readln

END.

 

            Рис. 3.4.

************* P={3,1,7,8,1} *****************