{Kartosanas metodes}

uses crt, dos;
const n=3000;
type mas=array[1..n] of longint;
var ar: mas;
    atsp, sella: integer;
    k,l :integer;
    start: word;

     procedure output(var ar:mas; l:integer);
     var i:integer;
     begin
          for i:=1 to k do write(ar[i],'   ');
     end;

     procedure maina(var a,b:longint);
     var c:integer;
     begin c:=a; a:=b; b:=c;
     end;

     function gettime:longint;
     var h,m,s,ms :word;
     begin
       dos.gettime(h,m,s,ms);
       gettime:=ms*100*(s+60*(m+60*h));
     end;

     procedure atspole(var ar:mas; n:integer; var atsp:integer);
     var i,j:integer;
     begin
     for i:=1 to n-1 do begin
         inc(atsp);
         if ar[i]<ar[succ(i)] then begin
           maina(ar[i],ar[succ(i)]);
           for j:=i downto 2 do
             if ar[pred(j)]<ar[j] then maina(ar[pred(j)],ar[j])
                          else break;
           end;
      end;
     write('Atspoles metode:');
     writeln(atsp,' salidzinasanas');
     end;

     procedure shella(var ar:mas; n:integer; var sella:integer);
     var i,j,k,step,y:integer;
     begin step:=1;
     while step<n do step:=3*step+1;
     step:=(step-1) div 3;
     repeat
     for k:=1 to step do
       begin inc(sella);
          i:=step+k;
          while i<=n do
            begin j:=i;
                y:=ar[j];
                while ar[j-step]<y do
                begin ar[j]:=ar[j-step];
                      j:=j-step;
                      if j<=step then break
                end;
          ar[j]:=y;
          i:=i+step;
          end;
      end;
     step:=(step-1) div 3;
     until step<1;
     write('Shella metode:');
     writeln(sella,' salidzinasanas');
     end;


begin
     clrscr; randomize;
     for l:=1 to n do begin
        ar[l]:=random(32767)-32678;end;
     sella:=0; atsp:=0;

     gettime;
     start:=gettime;
     shella(ar, n ,sella);
     writeln('Laiks ir ',gettime-start,'ms');
     writeln;

     gettime;
     start:=gettime;
     atspole(ar, n, atsp);
     writeln('Laiks ir ',gettime-start,'ms');

readkey;
end.