#include <iostream.h>
//#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <unistd.h>
//#include <time.h>


int PSIZE=5;
//const int SIZE=5000;
int BCASE;
int count=0;
int temp;

int find(int* array,int size,int k);


int compareint(const void* a,const void* b)
{
  if(*(int*)a<*(int*)b)
    return -1;
  else if(*(int*)a==*(int*)b)
    return 0;

  return 1;
}

int basecase(int psize)
{
  if(psize>49)
    return psize*2+1;
  return 30;
  

}


inline int ssort(int* array,int size,int k)
{
  register int i,j,pos=0,t;
  int min;

  for(i=0;i<k;i++)
    {
    
      min=array[i];
      pos=i;
      for(j=i;j<size;j++)
	{
	  if(array[j]<min)
	    {
	     
	      min=array[j];
	      pos=j;
	    
	    }
	}
      
      array[pos]=array[i];
      array[i]=min;
     
    }
  return array[k-1];
}




int find1(int* array,int size,int k)
{
  register int i;


  // base case
  
  if(size<=BCASE)
    {
      cout << "Executing the base case";
      cout.flush();
      cout << "\nSize : " << size;
      cout.flush();
      //            qsort(array,size,sizeof(int),compareint);
      cout << "\nk= " << k;
      cout.flush();
      //return array[k-1];
      return ssort(array,size,size-k+1);
    }


  cout << "\nSorting the partitions";
  cout.flush();

  int np=size/PSIZE;
  for(i=0;i<np;i++)
    {
      qsort(array+i*PSIZE,PSIZE,sizeof(int),compareint);
    }


  cout << "\nCollecting the middles";
   cout.flush();
   //__collect the medians
  int* middles=new int[np];
  //int middles[np];
  for(i=0;i<np;i++)
    {
      middles[i]=array[i*PSIZE+PSIZE/2];
    }

  int median=find(middles,np,np/2+1);
  //int median=middles[random() % np];
  delete[] middles;

  cout << "\nDividing the sets";
 
  cout.flush();
 //_______Now divide into sets
  int* set1=new int[size];
  int* set2=new int[size];
 
  //int set1[3*size/4];
  //int set2[3*size/4];
  int nset1=0,nset2=0;

   cout << "\nmaking sets";
 
   cout.flush();
  
  for(i=0;i<size;i++)
    {
      if(array[i]<median)
	set1[nset1++]=array[i];
      else
	set2[nset2++]=array[i];
    }

  
  //cout << endl << double(nset1)/size << " "  << double(nset2)/size;

  //cout << "deleteing array";

  //cout.flush();
  //delete[] array;
  
if(nset1<k)
    {
      cout << "\nCalling first find";
 
      cout.flush();
      delete[] set1;
    
      int ans=find(set2,nset2,k-nset1);
      delete[] set2;
      return ans;
    }

  cout << "\nCalling second find";
 
  cout.flush();
  
  delete[] set2;
  int ans= find(set1,nset1,k);
  delete[] set1;
  return ans;

}
      


int find(int* array,int size,int k)
{
  register int i;



  // base case
  
  if(size<=BCASE)
    {
      //cout << "Executing the base case";
      //cout.flush();
      //cout << "\nSize : " << size;
      //cout.flush();
      //            qsort(array,size,sizeof(int),compareint);
      //cout << "\nk= " << k;
      //cout.flush();
      //return array[k-1];
 
      return ssort(array,size,size-k+1);
      
    }


  //cout << "\nSorting the partitions";
  //cout.flush();


  int np=size/PSIZE;
  int* middles=new int[np];
  for(i=0;i<np;i++)
      middles[i]=ssort(&array[i*PSIZE],PSIZE,PSIZE/2+1);
  

  int median=find(middles,np,np/2+1);
  delete[] middles;

  //cout << "\nDividing the sets";
 
  //cout.flush();
 //_______Now divide into sets
  //int* set1=new int[size];
  //int* set2=new int[size];
  
  //int* set=new int[size*2];

  int nset1=0,nset2=0;

  // cout << "\nmaking sets";
  //  cout.flush();
  int *set=new int[size*2];
  
  for(i=0;i<size;i++)
    {
      temp=array[i];
      if(temp<median)
	set[nset1++]=temp;
      else
	set[size+nset2++]=temp;
    }

  if(nset1==0 || nset2==0)
    {
   
      delete[] set;
      return array[0];

    }
  
  
  
  //cout << endl << double(nset1)/size << " "  << double(nset2)/size;

  //cout << "deleteing array";
  //cout.flush();
  //delete[] array;
  
if(nset2<k)
    {
     
      
      int ans=find(set,nset1,k-nset2);
      delete[] set;
      return ans;
    }


  int ans= find(&set[size],nset2,k);
  delete[] set;
  return ans;

}
      

void run(int size,int k)
{
  int* array=new int[size+1];

  clock_t ct1,ct2;
  int i;

  //  cout << endl;
  for(i=0;i<size;i++)
    {
    
      array[i]=random();
      //   cout << array[i] << " " ;
    }


  timeval t1,t2;
  gettimeofday(&t1,NULL);
  int ans=find(array,size,k);
  gettimeofday(&t2,NULL);
  
  long timediff=(t2.tv_sec-t1.tv_sec)*1000000 + (t2.tv_usec-t1.tv_usec);
  
  
  // gettimeofday(&t1,NULL);
  //qsort(array,size,sizeof(int),compareint); 
  //gettimeofday(&t2,NULL);
  
  //long timediff1=(t2.tv_sec-t1.tv_sec)*1000000 +(t2.tv_usec-t1.tv_usec);
  ///cout << "\n"  << k << " largest element is : " << ans;
  //cout << "\n" << "By qsort answer is : " << array[size-k];


  //   cout << endl << size << "\t" << timediff //<< "\t" << timediff1;

  //printf("\n%d\t%ld\t%f",size,timediff,double(timediff)/size);//,timediff1);
  cout << endl << size << "\t" << timediff << "\t" << double(timediff)/size;
  /*  long usec=(long)(((double(ct2-ct1)/CLOCKS_PER_SEC)*1000000));
      printf("\n%d\t%ld\t%f\t%ld",size,usec,double(usec)/size,ct2-ct1);
  */  delete[] array;
  return;
}




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


  int size;
  if(argc>1)
    PSIZE=atoi(argv[1]);
  
  cout << "\n# Partition Size : " << PSIZE;

  BCASE=basecase(PSIZE);
  // run(size,size/2);
  
    int i=0;
    for(i=1000;i<=100000;i+=1000)
       {
	 run(i,i/2);
	 
	 }

  
    /*
    for(i=3;i<501;i+=2)
      {
	PSIZE=i;
	BCASE=basecase(PSIZE);
	run(50000,25000);
	}
    */



    // PSIZE=11;
    //run(10000,5000);
     //    count=0;
     //run(41010,41010/2);
    // printf("\ncount=%d",count);
}