// Finds the kth element in an unsorted table by qsort (slow)
// or using quicksort-style partitioning (usually fast)
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <sys/resource.h>

float elapsedCPU()
{
struct rusage rusage;
getrusage(RUSAGE_SELF,&rusage);
return rusage.ru_utime.tv_sec+rusage.ru_utime.tv_usec/1000000.0
  + rusage.ru_stime.tv_sec+rusage.ru_stime.tv_usec/1000000.0;
}

int generateRandom(minRange,maxRange)
int minRange,maxRange;
{
/* returns integer in range minRange <= x <= maxRange*/
return minRange+abs(random()) % (maxRange-minRange+1);
}

void generateRandomTable(int *arr,int n,int maxrange,int seed)
{
int i;

srandom(seed);
for (i=0;i<n;i++)
  arr[i]=generateRandom(0,maxrange);
}

int partition(int *arr,int p,int r)
// From CLRS, 2nd ed.
{
int x,i,j,temp;

x=arr[r];
i=p-1;
for (j=p;j<r;j++)
  if (arr[j]<=x)
  {
    i++;
    temp=arr[i];
    arr[i]=arr[j];
    arr[j]=temp;
  }
temp=arr[i+1];
arr[i+1]=arr[r];
arr[r]=temp;
return i+1;
}

int quickSelection(int *arr,int n,int k)
{
int lowRange,highRange,q;

lowRange=0;
highRange=n-1;
while (lowRange<=highRange)
{
  //printf("quickSelection subscript range %d..%d\n",lowRange,highRange);
  q=partition(arr,lowRange,highRange);
  if (k-1==q)
    return q;
  else if (k-1<q)
    highRange=q-1;
  else
    lowRange=q+1;
}
printf("quickSelection error\n");
exit(0);
}

int intCompare(const void* xin, const void* yin)
{
int *x,*y;

x=(int*) xin;
y=(int*) yin;
return (*x) - (*y);
}

int main()
{
int i;
int seed,n,k,maxrange;
int *a;
float startCPU;

printf("enter seed, n, k, maxrange: ");
fflush(stdout);
scanf("%d %d %d %d",&seed,&n,&k,&maxrange);
a=(int*) malloc(n*sizeof(int));
if (a==NULL)
  exit(0);

generateRandomTable(a,n,maxrange,seed);

startCPU=elapsedCPU();
printf("quickSelection:  The value with rank %d is %d\n",
  k,a[quickSelection(a,n,k)]);
printf("Time used is %f\n", elapsedCPU()-startCPU);

generateRandomTable(a,n,maxrange,seed);

startCPU=elapsedCPU();
qsort(a,n,sizeof(int),intCompare);
printf("qsort: The value with rank %d is %d\n",k,a[k-1]);
printf("Time used is %f\n", elapsedCPU()-startCPU);
}