program ex(input,output);
type cell = record
              x: integer;
              y: integer;
           end;
var i,n,t,k,c:integer;
var a:array[0..100000] of cell;
{Procedure quick sorts array a by the x field}
procedure quick(l,r:integer);
  var m:integer;
  function  partition(l,r:integer):integer;
    label 10;
    var i,j,x:integer;
    begin {partition}
      x:=a[l].x;
      i:=l; j:=r+1;
      while i<j do begin
        repeat j:=j-1; if i=j then goto 10; c:=c+1 until a[j].x<x;
        a[i].x:=a[j].x;
        repeat i:=i+1; if i=j then goto 10; c:=c+1 until a[i].x>x;
        a[j].x:=a[i].x; 
      end; 
      10: a[i].x:=x; partition:=i;
    end;
  begin {quick}
    if l<r then begin 
      m:=partition(l,r);
      quick(l,m-1);
      quick(m+1,r);
    end 
  end;
begin {main}
  write('input size ');
  read(n); 
  {c counts the number of comparisons}
  c:=0;
  for i:=1 to n do a[i].x:=trunc(random(1)*1000000);
  for i:=1 to n do a[i].y:=trunc(random(1)*1000000);
  t:=clock;
  quick(1,n);
  writeln('time=  millisec',clock-t);
  writeln('c= ',c);
  for i:=1 to 10 do write(a[i].x);
  writeln;
end.
