#include <iostream>
#include <cstring>
#include <cstdlib>
#include <sys/time.h>
using namespace std;
double my_clock2()
{
	  struct timeval tv;
	    gettimeofday(&tv, NULL);
	      return tv.tv_sec + (double)tv.tv_usec*1e-6;
}

void quick_sort(int *p,int lo,int hi)
{
  int i=lo;
  int j=hi;
  int k=p[(i+j)/2];
  while(i <= j){
     while(i <= hi && p[i] < k){
	     i++;
     }
     while(j>lo && p[j] > k){
	     j--;
     }
     if(i<=j){
	     int tmp = p[i];
	     p[i] = p[j];
	     p[j] = tmp;
	     i++;
	     j--;
     }
  }
  if(lo < j){
	  quick_sort(p,lo,j);
  }
  if(i < hi){
	  quick_sort(p,i,hi);
  }
  return;
}
  


int main(int argc, char *argv[])
{
  int numSort;
  

  if (argc != 2) {
    cout << "Please Input Sorting Num:";
    cin >> numSort;

    cout << numSort << '\n';
    //cout << "Error" << '\n';
    //exit(1);
  } else{

  numSort = atoi(argv[1]);
 } 
  int *p;
  int i;
  p = new int [numSort];
  for( int ir=0; ir< numSort; ir++){
	  p[ir]=rand();
  }
  i=numSort-1;
  double t1,t2;
  t1=my_clock2();
  
  quick_sort(p,0,i);

  t2=my_clock2();
  for( int ir=0; ir< numSort; ir++){
	  cout << p[ir] << '\n';
  }

  printf("elapsed time=%10.6f\n",t2-t1);
  delete [] p;
  return 0;
}