#include <stdio.h>
#include <math.h>
struct cell {
  int x;
  int y;
};
int i,n,t,k,c;
struct cell a[1000000];
int partition(l,r)
  int l,r;
{ int i,j;
  int x=a[l].x;
  i=l; j=r+1;
  while (i<j) {
    do {j--; if (i==j) goto exit; c++;} while (a[j].x>=x);
    a[i].x=a[j].x;
    do {i++; if (i==j) goto exit; c++;} while (a[i].x<=x);
    a[j].x=a[i].x; 
  }
  exit: a[i].x=x; return i;
}
/* function quick sorts array a by the x field */
quick(l,r)
  int l,r;
{ int m; 
  if (l<r) {
    m=partition(l,r);
    quick(l,m-1);
    quick(m+1,r);
  }
}
main()
{ printf("input size \n");
  scanf("%d",&n); 
/* c counts the number of comparisons */
  c=0;
/*  for (i=1;i<=n;i++) scanf("%d",&a[i]); */
  for (i=1;i<=n;i++) a[i].x=random()%100000;
  for (i=1;i<=n;i++) a[i].y=random()%100000;
  t=clock();
  quick(1,n);
  printf("\n");
  printf("time= %d millisec\n",(clock()-t)/1000);
  printf("c= %d \n",c);
  for (i=1;i<=10;i++) printf("%d ",a[i].x);
  printf("\n");
}
