//
//  In this example we sort only arrays of ints
//    See pages 347--353 of Budd's book

#include <iostream.h>
#include <stdlib.h>    // srand(), rand()
#include <time.h>      // system time for random seed
#include <math.h>      // log

// this is a macro, it saves a function call

#define log2( x ) ( log(x)/log(2) )

// fill the array with random numbers

int swap_count = 0;    // global variable

const int MAX_ARRAY_ELT = 100;

void fill_random( int a[], int size ); 

void print_array( int a[], int size ); 

void quicksort( int a[], int low, int high );

int pivot( int a[], int start, int stop, int pos );

bool is_sorted( int a[], int size );

void swap( int& x, int& y ){
  #ifdef DEBUG
    cout << "      swap: " << x << " " << y << endl; 
  #endif
  int z = x;
  x = y;
  y = z;
  swap_count++;
}  

int pivot( int a[], int start, int stop, int pos ){
  #ifdef DEBUG
    cout << "    pivot: " << start << " " << stop << " " << pos << endl;
  #endif   
  


  #ifdef DEBUG
    cout << "   pivot return: " << low << endl;
  #endif
 
  return low;   
}

void fill_random( int a[], int size ){
  for( int i=0; i < size; i++ )
    a[i] = rand() % MAX_ARRAY_ELT; 
}

void print_array( int a[], int size ){
  for( int i=0; i < size; i++ )
    cout << a[i] << " " ;
  cout << endl;
}

const int NUM_TESTS = 100;

int main(){

  srand( time(NULL) );          // random seed set to system time
    
  int n;
  cout << "Enter array size: ";
  cin >> n ;

  int* arr = new int[n];

  /*  // pivot test
  fill_random( arr, n );
  print_array( arr, n );
  pivot( arr, 0, n-1, n/2 );
  print_array( arr, n );
  quicksort( arr, 0, n-1 );
  print_array( arr, n ); */
  
  for( int i=0; i < NUM_TESTS; i++ ){  
      fill_random( arr, n );
      quicksort( arr, 0, n-1 ); 
      // print_array( arr, n ); 
      if( is_sorted( arr, n ) ) cout << "OK ";
      else cout << "ERROR! ";
  }

  cout << "\n Swaps: " << swap_count << endl;
  cout << " Theory predicts O(n log2(n)): " << n*log2(n)*NUM_TESTS << endl;   
  delete[] arr;
  return 0;
}

// apply the pivot recursively to the part of array between low and high
// Principle: divide and conquer.

void quicksort( int a[], int low, int high ){
  #ifdef DEBUG
   cout << "quicksort: " << low << "  " << high << endl;
  #endif

  //              
  //  * * ... * * ... * * ... * * * *
  //          ^       ^         ^ 
  //         low    pivot      high
  //          

}

// check if an array is sorted

bool is_sorted( int a[], int size ){
 
  for( int i=0; i < size-1 ; i++ )
    if( a[i] > a[i+1] ) return false;

  return true;  // if we got here, no problem
}