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

int PSIZE=5;

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 find(int* array,int size,int k)
{
  register int i; 
  if(size<=BCASE) 
      return ssort(array,size,size-k+1);
      

  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;

  int nset1=0,nset2=0;

  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];

    }
  
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;


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


  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);
  cout << endl << PSIZE << "\t" << timediff << "\t" << double(timediff)/size;
  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);
  
  int i=0;

  /*
  for(i=1000;i<=100000;i+=1000)
    {
      run(i,i/2);
	 
      }*/


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

  
  
}