// Quick sort
// Programmer: E. Kaltofen (December 8, 1992)
#include <stdlib.h>
#include <stdio.h>
// extern "C" long random();
// extern "C" void srandom(int);
// for multiple random generators in same program
// extern "C" char *initstate(unsigned, char*, int);
// extern "C" char *setstate(char*);

#ifdef DEBUG
#include <iostream.h>
#endif
typedef int ElType; // for testing purposes
int insort(ElType[], int);

const int BREAKEVEN = 1; // size at which insertion sort outdoes quicksort
                         // for testing purposes set to 1
int quicksort(ElType A[], int p, int q)
// sorts the array segment A[p],...,A[q] into < order
// note: one must have ElType operator<(ElType)
// returns the number of comparisions
{int i, j, r, comp = 0;
 ElType x, tmp;

#ifdef DEBUG
 printf("QS on A[%2d,...,%2d] ", p, q);
#endif

 // escape if segement too small
 if(p >= q){
#ifdef DEBUG
    printf("\n");
#endif
    return 0;}; // insort returns -1 for negative size

 if(q-p+1 <= BREAKEVEN){
#ifdef DEBUG
   for(i=0; i<p; i++) printf("   ");
   for(i=p; i<=q; i++) printf("%2d ", A[i]);
   printf("\n");
#endif
   return insort( &A[p], q-p+1 );};

 // select an index between p and q
 r = p  + (random() % (q-p+1)); // random index selection
 x = A[r];
 // move this element into first position (for later partition to work correctly)
 tmp = A[p]; A[p] = x; A[r] = tmp;

 // Partition phase:
 // move elements so that all elements in A[p],...,A[j-1] no smaller than
 // x = A[j], which is no larger than the elements in A[j+1],...,A[q-1].
 i = p; j = q+1;
 for(;;) // will break out of this infinite loop
   {do {j--;  comp++;}
    while(x < A[j]);
    // now A[j] <= x and A[j+1],...,A[q] >= x; must stop because A[p] = x
    do {i++; }
    while( i <= q && (++comp && A[i] < x) );
    // now A[i] >= x (or i==q+1) and A[p+1],...,A[min(i,q)] <= x
    // Note: the test i<=q can be avoided if it is known that A[q+1] is
    //       no smaller than all A[p], A[p+1],..., A[q]. This can be
    //       arranged by initially moving the largest element to A[n-1]
    //       and then sorting quicksort(A, 0, n-2).
    if( i >= j) break;
    tmp = A[i]; A[i] = A[j]; A[j] = tmp;
   }; // end while
 A[p] = A[j]; // <= x
 A[j] = x;

#ifdef DEBUG
 // i is not used any more
 for(i=0; i<p; i++) printf("   ");
 for(i=p; i<=q; i++) printf("%2d ", A[i]);
 printf("\n");
 printf("Pivot element      ");
 for(i=0; i<j; i++) printf("   ");
 printf("%2d \n", A[j]);
#endif

 // recursion on sub-segments
 if (p < j-1) comp += quicksort(A, p, j-1);
 if (j+1 < q) comp += quicksort(A, j+1, q);
 return comp;
}// end quicksort

#include <iostream.h>
main(int argc, char** argv)
// run as "a.out 100 25 <seed1> <seed2>", where 100 is the size to be tested,
// and 25 is the range of entries
{int *array; int comp, i, size, mod;
 int seed1 = 101;
 int seed2 = 101;
 // state for random
 static long state1[32] = {
   3,
   0x9a319039, 0x32d9c024, 0x9b663182, 0x5da1f342,
   0x7449e56b, 0xbeb1dbb0, 0xab5c5918, 0x946554fd,
   0x8c2e680f, 0xeb3d799f, 0xb11ee0b7, 0x2d436b86,
   0xda672e2a, 0x1588ca88, 0xe369735d, 0x904f35f7,
   0xd7158fd6, 0x6fa6f051, 0x616e6b96, 0xac94efdc,
   0xde3b81e0, 0xdf0a6fb5, 0xf103bc02, 0x48f340fb,
   0x36413f93, 0xc622c298, 0xf5a42ab8, 0x8a88d77b,
   0xf5ad9d0e, 0x8999220b, 0x27fb47b9 };
 if (argc < 3)
    {cerr << "Call as \"" << argv[0] << " <size> <mod> {<seed1> {<seed2>}}\"" << endl;
     exit(1);};
 sscanf(argv[1], "%d", &size); sscanf(argv[2], "%d", &mod);
 if(argc > 3) sscanf(argv[3], "%d", &seed1);
 if(argc > 4) sscanf(argv[4], "%d", &seed2);
 srandom(seed1);
 array = new int[size];
 cout << "Input array" << endl;
 for(i = 0; i < size; i++) {array[i] = random() % mod; cout << array[i] << " ";};
 cout << endl;
 initstate(seed2, (char*)state1, 128);
 setstate((char*)state1);
 comp = quicksort(array, 0, size-1);
 cout << "Quick sorted array after " << comp << " comparisons" << endl;
 for(i = 0; i < size; i++) cout << array[i] << " "; cout << endl;
}