#include <stdio.h>
#include <stdlib.h>
#if __ALPHA
  #include <sys/times.h>
#else
  #include <sys/time.h>
#endif
#include <sys/resource.h>

#define NUMELEMENTS (2000000)

int a[NUMELEMENTS],b[NUMELEMENTS];
int c[128];

#define generateRandom(minRange,maxRange) \
  (minRange)+abs(random()) % ((maxRange)-(minRange)+1)

#if __ALPHA
float CPUtime()
{
  struct tms buf;
  times(&buf);
  return ((float) clock())/CLOCKS_PER_SEC;
}

float elapsedTime()
{
  struct tms buf;
  return ((float) times(&buf))/CLK_TCK;
}
#else
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;
}

float elapsedTime()
{
  return (10000.0*times(NULL))/CLOCKS_PER_SEC;
}
#endif

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

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

main()
{
unsigned int seed;
int i;
float startCPU,stopCPU;
float startTime,stopTime;

printf("enter seed\n");
scanf("%u",&seed);
srandom(seed);
for (i=0;i<NUMELEMENTS;i++)
  a[i]=generateRandom(0,2097151);
startTime=elapsedTime();
startCPU=CPUtime();
qsort(a,NUMELEMENTS,sizeof(int),intSort);

stopTime=elapsedTime();
stopCPU=CPUtime();
printf("qsort elapsed time %f\n",stopTime-startTime);
printf("qsort CPU time %f\n",stopCPU-startCPU);
printf("samples:\n");
for (i=0;i<NUMELEMENTS;i+=1000000)
  printf("a[%d]=%d\n",i,a[i]);

srandom(seed);
for (i=0;i<NUMELEMENTS;i++)
  a[i]=generateRandom(0,2097151);

startTime=elapsedTime();
startCPU=CPUtime();
for (i=0;i<128;i++)
  c[i]=0;
for (i=0;i<NUMELEMENTS;i++)
  c[a[i]%128]++;
for (i=1;i<128;i++)
  c[i]+=c[i-1];
for (i=NUMELEMENTS-1;i>=0;i--)
  b[--c[a[i]%128]]=a[i];

for (i=0;i<128;i++)
  c[i]=0;
for (i=0;i<NUMELEMENTS;i++)
  c[(b[i]/128)%128]++;
for (i=1;i<128;i++)
  c[i]+=c[i-1];
for (i=NUMELEMENTS-1;i>=0;i--)
  a[--c[(b[i]/128)%128]]=b[i];

for (i=0;i<128;i++)
  c[i]=0;
for (i=0;i<NUMELEMENTS;i++)
  c[a[i]/16384]++;
for (i=1;i<128;i++)
  c[i]+=c[i-1];
for (i=NUMELEMENTS-1;i>=0;i--)
  b[--c[a[i]/16384]]=a[i];

stopTime=elapsedTime();
stopCPU=CPUtime();
printf("radix/count elapsed time %f\n",stopTime-startTime);
printf("radix/count sort CPU time %f\n",stopCPU-startCPU);
printf("samples:\n");
for (i=0;i<NUMELEMENTS;i+=1000000)
  printf("b[%d]=%d\n",i,b[i]);
}