program new;

uses dos, crt;

const NMax=15000;

type Mas=array[1..NMax]of integer;
     Tim=array[1..4] of word;

var t,t1,t2:Tim;{t.k. <0}
    s:array[1..4] of string;{dlya udobstva vyvoda vremeni}
    z,y:integer;{isp pri vyvode vremeni kak s4et4iki cikla}
    n:integer;{dlina massiva}
    k:integer;{s4et4ik cikla pri vvode massiva do 10-i elementov}
    j:integer;{s4et4ik cikla pri vyvode neotsort massiva}
    m:integer;{s4et4ik cikla dlya otstupa sverhu v menu}
    c,d:char;{dlya keysa}
    a,b:Mas;{massiv}
    x:word;{iskomyi element}
    l,f1,f2,f3,f4,f5,f6:integer;{s4et4iki cikla}
    w:integer;{nomer iskomogo elementa}
label menu,e1,e2,e3,e5,p1,p3;


{------------------------------------Functions&Procedures--------------------------------}

{na4alo pods4eta vremeni}
procedure ntime;
begin
    gettime(t1[1],t1[2],t1[3],t1[4]);
end;

{konec pods4eta vremeni}
procedure ftime(t1:Tim);
begin
    gettime(t2[1],t2[2],t2[3],t2[4]);
    t[1]:=t2[1]-t1[1]; if t[1]<0 then t[1]:=t[1]+23;
    t[2]:=t2[2]-t1[2]; if t[2]<0 then t[2]:=t[2]+59;
    t[3]:=t2[3]-t1[3]; if t[3]<0 then t[3]:=t[3]+59;
    t[4]:=t2[4]-t1[4]; if t[4]<0 then t[4]:=t[4]-65500;
end;

{vyvod vremeni}
procedure vtime(t:Tim);
begin
    for z:=1 to 4 do str(t[z],s[z]);
    for y:=1 to 4 do if length(s[y])=1 then s[y]:='0'+s[y];
    write(s[1],':',s[2],':',s[3],'.',s[4]);
end;

{lineinyi poisk}
function LinSearch(var b:Mas;n,x:integer):word;{b-massiv,n-dlina massiva,x-iskomyi element}
var i:integer;{s4et4ik}
begin
    LinSearch:=0;
    for i:=1 to n do begin
        if b[i]=x then begin
	   LinSearch:=i;{nomer iskomogo elementa}
           w:=i;
	end;
    end;
end;

{dvoi4nyi poisk}
function BinSearch(var b:Mas; n,x:integer):word;
Var left,right,i:integer;
begin
    left:=1; right:=n;
    while left<=right do begin
        i:=(left+right) div 2;
        if b[i]=x then break
        else if b[i]<x then left:=i+1
        else right:=i-1;
    end;
        if b[i]=x then BinSearch:=i else BinSearch:=0;
end;

{sortirovka puzirkom}
procedure bubble(var b:Mas;n:integer);
var i,j:integer;{s4et4iki dlya sortirovki}
    v1,v2:integer;{s4et4iki dlya vyvoda}
    tmp:integer;{promezhuto4naya peremennaya}
begin
    ntime;
    for i:=n downto 2 do begin
	for j:=1 to n-1 do begin
	    if b[j]>b[j+1] then begin
		tmp:=b[j]; b[j]:=b[j+1]; b[j+1]:=tmp;
    	    end;
	end;
    end;
    ftime(t1);
    write('Ish massiv: ');
    for v1:=1 to n do begin
	write(a[v1],' ');
    end;writeln('');
    write('Otsortirovannyi massiv ');
    for v2:=1 to n do begin
	write(b[v2],' ');
    end;
    writeln('');
    write('Otsortirovan za: ');vtime(t);
    readln;
end;

{sortirovka vyvborom}
procedure select(var b:Mas;n:integer);
var i,j:integer;{s4et4iki dlya sortirovki}
    v1,v2:integer;{s4et4iki dlya vyvoda}
    tmp:integer;{promezhuto4naya peremennaya}
begin
    ntime;
    for i:=1 to n do begin
	for j:=i to n-1 do begin
	    if b[j+1]<b[j] then begin
		tmp:=b[i]; b[i]:=b[i+1]; b[i+1]:=tmp;
	    end;
	end;
    end;
    ftime(t1);
    write('Ish massiv: ');
    for v1:=1 to n do begin
	write(a[v1],' ');
    end;writeln('');
    write('Otsortirovannyi massiv ');
    for v2:=1 to n do begin
	write(b[v2],' ');
    end;
    writeln('');
    write('Otsortirovan za: ');vtime(t);
    readln;
end;
{sortirovka vklu4eniem}
procedure insert(b:Mas;n:integer);
var i,j,k:integer;{s4et4iki dlya sortirovki}
    v1,v2:integer;{s4et4iki dlya vyvoda}
    tmp:integer;{promezhuto4naya peremennaya}
begin
    ntime;
    j:=2;
    while j<=n do begin
	i:=j;k:=0;
	while (i>=2)and(k=0) do begin
	    if b[i-1]>b[i] then begin
		tmp:=b[i-1];b[i-1]:=b[i];b[i]:=tmp;
	    end;
	inc(i);
	end;
    dec(j);
    end;

    ftime(t1);
    write('Ish massiv: ');
    for v1:=1 to n do begin
	write(a[v1],' ');
    end;writeln('');
    write('Otsortirovannyi massiv ');
    for v2:=1 to n do begin
	write(b[v2],' ');
    end;
    writeln('');
    write('Otsortirovan za: ');vtime(t);
    readln;
end;
{bystraya sortirovka}
procedure quick(var b:Mas; min,max:integer);
var i,j,p,tmp:integer;
begin
  if min<max then begin
    i:=min; j:=max; p:=b[j];
    while i<j do begin
       while (i<j)and(b[i]<=p)do inc(i);
       while (i<j)and(b[j]>=p)do dec(j);
       if i<j then begin tmp:=b[i]; b[i]:=b[j]; b[j]:=tmp; end;
    end;
    tmp:=b[i]; b[i]:=b[max]; b[max]:=tmp;
    quick(b,min,l-1);
    quick(b,min,max);
  end;
end;
{taimer k bysroi sortirovke}
procedure qs;
begin
    b:=a;
    ntime;
    quick(b,1,n);
    ftime(t1);
end;
{-----------------------------------------PROGRAM----------------------------------------}

begin

randomize;
e5:  clrscr;
    write('Vvedi dlinu massiva: ');readln(n);
    if n>NMax then begin
        writeln('Owibka vvoda');
        readln;
        goto e5;
    end;
    if n<=10 then begin
	for k:=1 to n do begin
	    writeln('Vvedi ',k,'-bli element massiva');readln(a[k]);
	end;
    end
    else begin
	for k:=1 to n do begin
	    a[k]:=random(4*n)-2*n;
	end;
    end;
    for j:=1 to n do write(a[j],'  ');
    readln;

    for l:=1 to n do begin
        b[l]:=a[l];
    end;
menu:
    clrscr;
    for m:=1 to 15 do begin
        writeln(' ');
    end;
    writeln('                                Poisk');
    writeln('                                   1. Lineinyi');
    writeln('                                   2. Dvoi4nyi');
    writeln(' ');
    writeln('                                Sortirovka');
    writeln('                                   3. Puzirkom');
    writeln('                                   4. Vyborom');
    writeln('                                   5. Vklu4eniem');
    writeln('                                   6. Bystrym metodom');
    writeln(' ');
    writeln('                                   7. Pokazat massiv');
    writeln('');
    writeln('                                   8. Exit');
e1: c:=readkey;
    if (c<'1') or (c>'8') then goto e1;
    case c of
        '1': begin
p1:		clrscr;
		writeln('VVedite element dlya poiska: ');readln(x);
		if LinSearch(b,n,x)=0 then begin
		   writeln('Takogo elementa net v massive');
		end
		else begin
		   writeln('Element ',x,' nahoditsa na ',w,'-om meste v massive');
		end;
		writeln('Prodolzhit poisk? y/n');
e2:             d:=readkey;
                if (d<>'y')and(d<>'n') then goto e2;
                case d of
                     'y':goto p1;
                     'n':goto menu;
                end;
          end;{1}
	  '2': begin
p3:		bubble(b,n);
		clrscr;
		writeln('VVedite element dlya poiska: ');readln(x);
		if BinSearch(b,n,x)=0 then begin
		   writeln('Takogo elementa net v massive');
		end
		else begin
		   writeln('Element ',x,' nahoditsa na ',w,'-om meste v massive');
		end;
		writeln('Prodolzhit poisk? y/n');
e3:             d:=readkey;
                if (d<>'y')and(d<>'n') then goto e3;
                case d of
                     'y':goto p3;
                     'n':goto menu;
                end;
          end;{2}
	  '3':begin
		clrscr;
		bubble(b,n);
		goto menu;
	  end;{3}
	  '4':begin
		clrscr;
		select(b,n);
		goto menu;
	  end;{4}
	  '5':begin
		clrscr;
		insert(b,n);
		goto menu;
	  end;
	  '6':begin
		clrscr;
		qs;
		goto menu;
	  end;{6}
          '7':begin
                clrscr;
                write('Ishodnyi massiv: ');
                for f1:=1 to n do begin
                    write(a[f1],'  ');
                end;
                writeln('  ');
                write('Kone4nyi massiv: ');
                for f2:=1 to n do begin
                    write(b[f2],'  ');
                end;
                readln;
                goto menu;
          end;{8}
          '8':halt;





    end;
end.