//Name:
//
// CSC120, Lab 1, Quick Sort
// Spring 2002
// driver for testing quick sort on array of points.
// The [points are soted according to distance from the origin
//
// In main() you must complete the missing code indicated with lines like
   /********** some letter **********/ 
// Also you must write and include at the end of this file the functions 
// implementing quick sort.


#include "stdinc.h"
#include "point.h"

//*************************************
//********* Pototypes *****************
//*************************************

int randint(int lo, int hi);       //returns a random integer between lo and hi

void QuickSort(Point* P, int p, int r);    // randomized Quick sort

//Partition procedure for Quick sort.
//Partitions array A between indices p and r with respect to the last element x
//Retrurns an index q, such that the result of the partition is 
//   A[i] <= x, for p<=i<=q
//   A[i] > x,  for q< i<=r

int  Partition(Point*, int p, int r); 

//*************************************
//********* Main program***************
//*************************************

int main()        
{
  int n;             //number of points

  Point *P,*Q;       // dynamic arrays of points.
                     // Q is used only for comparison when testing the program

// Use these line if you want a different random set of points for each
//   run.  What this does is use the system clock as the seed to the
//   random number generator.  For the version used to create the submitted
//   output, you should NOT use these lines.
//
// int seed;
// time_t tp;
// time(&tp);			  // get the system time
// seed = tp;                     // use it as a seed for
// srand(seed);                   //   the random number generator

  cout << "How many points? ";
  cin >> n;
  
  /****** a ************/     //allocate space for dynmic array P of n Points
  /****** b ************/     // allocat space for dynamic array Q of n Points

  for (int i=0; i<n; i++){       //initialize P
    P[i].x(randint(1,100000));   // set P[i-1].x to a random integer
    P[i].y(randint(1,100000));
  }

  /******* c ************/    // copy array P in Q

  /******* d ************/    // call QuickSort to sort the array P 
  
  if (n <= 25){
    cout << "The unsorted array was:" << endl;
    /******** e ********/     // Print the unsorted array of points, Q

    cout << "The sorted array is:" << endl;
    /******** f ********/     // Print the sorted array of points, P
  }

  //free the space allocated for P and Q
  delete [] P;        
  delete [] Q;        
  return 0;        //successful completion
}

//***********************************
//********* Function Definitions*****   
//***********************************   

int randint(int lo, int hi)    //returns a random integer between lo and hi
{
  //drand48() returns rand double between 0 and 1
  return int( 0.5 + lo + (drand48() * (hi - lo)) );
}

// IF the system you compile on does not have drand48() try the following
// version of randint, which uses only rand().
// We obtain a random double between 0 and 1 by
// (1 - double(rand())/RAND_MAX, where RAND_MAX is predefined constant, at
// least 16-bit interger.
// If you are going to use this version uncomment it, i.e. remove /* and */
// but comment the previous version, i.e., include it between /* and */

/*

int randint(int lo, int hi)    //returns a random integer between lo and hi
{

  //drand48() returns rand double between 0 and 1
  return int( 0.5 + lo + (1 - double(rand())/RAND_MAX)* (hi - lo));
}

*/