// Finds the k largest elements 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;
}

void quickLargest(int *arr,int n,int k)
{
int low,high,q;

low=0;
high=n-1;
while (1)
{
  printf("quickLargest subscript range %d..%d\n",low,high);
  q=partition(arr,low,high);
  if (q<n-k-1)
    low=q+1;
  else if (q>n-k)
    high=q-1;
  else
    return;
}
}

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

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

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

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();
quickLargest(a,n,k);
stopCPU=elapsedCPU();
printf("quickLargest:  The %d largest values are:\n",k);
for (i=n-k;i<n;i++)
  printf("%d\n",a[i]);
printf("Time used is %f\n",stopCPU-startCPU);

generateRandomTable(a,n,maxrange,seed);

startCPU=elapsedCPU();
qsort(a,n,sizeof(int),intCompare);
stopCPU=elapsedCPU();
printf("qsort: The %d largest values are:\n",k);
for (i=n-k;i<n;i++)
  printf("%d\n",a[i]);
printf("Time used is %f\n",stopCPU-startCPU);
}