/*********************************/
/*          quicksort.c          */
/*                               */
/*********************************/

#include <stdio.h>
#include <time.h>

#define  MAXNUM   1000
#define  COUNT    100
#define  MODULUS  ((long)0x20000)
#define  C        13849L
#define  A        25173L

long  seed = 7L;

long  random();

long  buffer[MAXNUM]={0};

void main()
   {
   int i,j;
   long  temp;
   clock_t  starttime,stoptime,benchtime;
   clock_t  nulltime;
   starttime = clock();
   stoptime  = clock();
   nulltime  = stoptime - starttime;

   printf("   Filling Array and Sorting %d Times\n",COUNT);

   starttime = clock();

   for(i=0;i<COUNT;++i)
   {
      for(j=0;j<MAXNUM;++j)
      {
         temp=random(MODULUS);
         if(temp<0L)
            temp=(-temp);
         buffer[j]=temp;
      }

      /*
      printf(" Buffer Full, Iteration %d\n",i);
      */

      quick(0,MAXNUM-1,buffer);
   }
      stoptime  = clock();
      benchtime = stoptime - starttime - nulltime;

      printf("   Done With Iteration %d\n",i);
      printf("   1/%dths of a second = %ld\n",CLOCKS_PER_SEC,benchtime);

   }

   quick(lo,hi,base)
      int   lo,hi;
      long  base[];

   {
      int i,j;
      long  pivot,temp;

      if(lo<hi)
      {

         for(i=lo,j=hi,pivot=base[hi];i<j;)
         {
         while( i<hi && base[i]<= pivot)
            ++i;
         while( j>lo && base[j]>= pivot)
            --j;
         if(i<j)
            {
            temp=base[i];
            base[i]=base[j];
            base[j]=temp;
            }
         }
      temp=base[i];
      base[i]=base[hi];
      base[hi]=temp;

      quick(lo,i-1,base);
      quick(i+1,hi,base);
      }
   return 0;
   }

   long  random(size)
      long  size;
      {
      seed=seed*A+C;
      return(seed % size);
      }
