// Quicksort & Templates
// By: Odis

// You can find some good information on the Quick Sort algorithm at
// http://en.wikipedia.org/wiki/Quick_sort

#include <cstdlib>
#include <iostream>
#include <time.h>

// Comment this out to turn off the array output
//#define DISPLAY_OUTPUT

// Change this to change the number of elements to be stored and sorted
#define ARRAY_LENGTH 600000

template< typename Type >
void quickSort( Type* array, int low, int high )
{
  int pivotPosition = -1;

  if ( low < high )
  {
    pivotPosition = partition(array, low, high);
    quickSort(array, low, pivotPosition-1);
    quickSort(array, pivotPosition+1, high );
  }
}

template< typename Type >
void swap( Type& x, Type& y )
{
  Type temp = x;

  x = y;
  y = temp;
}

template< typename Type >
int partition( Type* array, int low, int high )
{
  int left, right;
  Type pivot;

  left = low;
  right = high;
  pivot = array[low];

  while ( left < right )
  {
    while ( array[right] > pivot )
      right--;

    while ( (left < right) && (array[left] <= pivot) )
      left++;

    if ( left < right )
     swap(array[left], array[right] );
  }

  array[low] = array[right];
  array[right] = pivot;

  return right;
}

int main()
{
    int array[ARRAY_LENGTH];
    int length = ARRAY_LENGTH;
    
    // for timing
    time_t start, end;

    // seed pseudo random number generator
    srand(time(NULL));

#ifdef DISPLAY_OUTPUT
    std::cout << "\nPicking random elements...\n";
#endif

    for ( int i = 0; i < ARRAY_LENGTH; i++ )
     array[i] = (rand() % 10000); /*for ints*/
//     array[i] = (rand() % 26)+(((rand() % 2) == 0) ? 97 : 65); /*for chars*/
//     array[i] = (rand()/(float(RAND_MAX)+1))*ARRAY_LENGTH; /*for floats*/

#ifdef DISPLAY_OUTPUT
    // print out unsorted
    std::cout << "\nUnsorted\n\n";
    for ( int i = 0; i < ARRAY_LENGTH; i++ )
    {
       std::cout << array[i];
       
       // print new lines or comma's
       if ( (i % 10) == 9 )
        std::cout << std::endl;
       else if ( i+1 < ARRAY_LENGTH )
        std::cout << ", ";
    }
#endif

    time(&start);
    
    // call the function to get everything started
    quickSort( array, 0, length-1 );
    
    time(&end);

#ifdef DISPLAY_OUTPUT
    std::cout << "\n\nSorted\n\n";

    for ( int i = 0; i < ARRAY_LENGTH; i++ )
    {
     std::cout << array[i];

     // print new lines or comma's
     if ( (i % 10) == 9 )
      std::cout << std::endl;
     else if ( i+1 < ARRAY_LENGTH )
      std::cout << ", ";
    }
#else
    std::cout << "\n\nNumber of random elements: " << ARRAY_LENGTH;
#endif

    std::cout << "\n\nTime: " << difftime(end,start) << std::endl << std::endl;


    return EXIT_SUCCESS;
}