using namespace std;
#include<iostream>
#include<stdlib.h>
#include<time.h>

/******  QuickSort ******/

// In this version of quicksort, the pivot is the first element out of
// order.  For example, in 3 5 8 6 9, the pivot is 8.  This way, if
// there is no pivot, then the list is already sorted, and if a pivot
// exists, the list can be divided into two non-empty partitions.

// Finding the index of the pivot, returns -1 if no pivot (already sorted)
// start and end defines inclusive range
int findpivot(int *A, int start, int end)
{
  int pi = -1;
  int i = start;
  while (pi<0 && i<end)
    {
      if (A[i]>A[i+1]) pi = i+1;
      i++;
    }
  return pi;
}


// partition: separate via swapping of an array into two parts, given
// start, end, pivot.  Returns start index of second partition.

int partition(int *A, int start, int end, int pivot)
{
  int i = start;
  int j = start;
  int temp;
  while (j<=end)
    {
      if (A[j] <= pivot)
	{
	  temp = A[i];
	  A[i] = A[j];
	  A[j] = temp;
	  i++;
	}
      j++;
    } // while
  return i;
}

void quicksort(int *A, int start, int end)
{
  int pi;
  int i;
  pi = findpivot(A,start,end);
  if (pi < 0) return;  // partition already sorted
  i = partition(A,start,end,A[pi]);
  quicksort(A,start,i-1);
  quicksort(A,i,end);
}

// Test procedure with timing.  The size of the array is determined
// by the first command-line argument:
int main(int argc, char **argv)
{
  int n;  // size of array, determined by command-line argument
  int *A; // array to be dynamically created
  clock_t t1, t2;  // for time measurements
  n = atoi(argv[1]);   // first command-line argument
  A = new int[n];
  for(int i=0;i<n;i++) A[i] = random();

  t1 = clock();   // record time
  quicksort(A,0,n-1);
  t2 = clock();   // record time

  delete(A);
  cout << "\ntime ~= " << (t2-t1)/((double)CLOCKS_PER_SEC) << " seconds\n";
  return 0;  
}