// Ordinary recursive quicksort
// See CLRS for details
#include <stdio.h>
#include <sys/time.h>
#include <sys/resource.h>

float CPUtime()
{
  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 *arr;
int arrSize;

int oldPartition(arr,p,r)
// From CLR, 1st edition
int *arr,p,r;
{
int x,i,j,temp;

/*
printf("Input\n");
for (i=p;i<=r;i++)
  printf("%d %d\n",i,arr[i]);
*/
x=arr[p];
i=p-1;
j=r+1;
while (1)
{
  while (arr[--j]>x);
  while (arr[++i]<x);
  if (i<j)
  {
    temp=arr[i];
    arr[i]=arr[j];
    arr[j]=temp;
  }
  else
  {
/*
    printf("Left output\n");
    for (i=p;i<=j;i++)
      printf("%d %d\n",i,arr[i]);
    printf("Right output\n");
    for (i=j+1;i<=r;i++)
      printf("%d %d\n",i,arr[i]);
*/
    return j;
  }
}
}

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

/*
printf("Input\n");
for (i=p;i<=r;i++)
  printf("%d %d\n",i,arr[i]);
*/

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;
/*
printf("Left output\n");
for (j=p;j<=i;j++)
  printf("%d %d\n",j,arr[j]);
printf("In final position\n");
printf("%d %d\n",i+1,arr[i+1]);
printf("Right output\n");
for (j=i+2;j<=r;j++)
  printf("%d %d\n",j,arr[j]);
*/
return i+1;
}

oldQuickSort(int *a,int p,int r)
{
int q;

if (p<r)
{
  q=oldPartition(a,p,r);
  oldQuickSort(a,p,q);
  oldQuickSort(a,q+1,r);
}
}

newQuickSort(int *a,int p,int r)
{
int q;

if (p<r)
{
  q=newPartition(a,p,r);
  newQuickSort(a,p,q-1);
  newQuickSort(a,q+1,r);
}
}

main()
{
int i;
unsigned seed;
float startCPU;

printf("enter number of keys\n");
scanf("%d",&arrSize);
arr=(int*) malloc(sizeof(int)*arrSize);
if (!arr)
{
  printf("malloc failed\n");
  abort();
}
printf("enter seed\n");
scanf("%u",&seed);
srandom(seed);
for (i=0;i<arrSize;i++)
  arr[i]=abs(random())%(1<<25);
startCPU=CPUtime();
printf("Running 2nd edition quicksort\n");
newQuickSort(arr,0,arrSize-1);
printf("CPU used is %f\n",CPUtime()-startCPU);
srandom(seed);
for (i=0;i<arrSize;i++)
  arr[i]=abs(random())%(1<<25);
startCPU=CPUtime();
printf("Running 1st edition quicksort\n");
oldQuickSort(arr,0,arrSize-1);
printf("CPU used is %f\n",CPUtime()-startCPU);
}