// File: QuickSort.cpp
// Quick Sort Implementation

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

using namespace std;

int Partition(int low,int high,int arr[]);
void Quick_sort(int low,int high,int arr[]);
void print(int arr[],int elts);
// A couple of global variables so we can show what's going on...
int global_n;
bool global_flag;

int main(int argc,char ** argv)
{ int *a,n,low,high,i;
  global_flag=(argc>1);
  cout<<"Enter number of elements:";
  cin>>n;
  a=new int[global_n=n];
/* Enter data manually 
  cout<<"enter the elements:";
  for(i=0;i<n;i++)
    cin>>a;
*/
// Generate data randomly
  srand(time(NULL));
  for(i=0;i<n;i++)
    a[i]=rand()%100;
  cout<<"Initial Order of elements:\n";
  print(a,n);
  // Set boundaries
  high=n-1;
  low=0;
  Quick_sort(low,high,a);
  cout<<"\nFinal Array After Sorting:\n";
  print(a,n);
}

void print(int arr[],int elts)
{ for(int i=0;i<elts;i++)
    cout<<arr[i]<<"	";
  cout<<"\n";
}

void Quick_sort(int low,int high,int arr[])
{
  int Piv_index,i;
  if(low<high)
  {
   Piv_index=Partition(low,high,arr);   // get pivot
   Quick_sort(low,Piv_index-1,arr);     // sort list below pivot
   Quick_sort(Piv_index+1,high,arr);    // sort list above pivot
  }
}


// Function for partitioning the array about a pivot
// Goal is to have all values l.t. pivot to its left, 
//              and all values g.t. pivot to its right
int Partition(int low,int high,int arr[])
{ int i,high_vac,low_vac,pivot/*,itr*/;
  if (global_flag)  cout << endl;
  // Initially, pivot is first element
  pivot=arr[low];
  while(high>low)
  { high_vac=arr[high];

    // Working right-to-left, 
    // find the first value in the list less than or equal to the pivot
    while(pivot<high_vac)
    { if(high<=low)             // if all values were g.t. pivot
        break;
      high--;
      // Set high_vac to value of rightmost item l.t. pivot
      high_vac=arr[high];
    }
    // Copy high_vac over the pivot;  
    //  every element to the right of high is larger than the pivot 
    arr[low]=high_vac; 
    
    // Now, work the same thing left to right, 
    //  determining all values l.t. pivot 
    low_vac=arr[low];
    // At end of loop, low is index of 1st value g.t. pivot
    while(pivot>low_vac)        // true the 1st time, unless while above broke
    { if(high<=low) 
        break;
      low++;
      low_vac=arr[low];
    }
    // copy 1st value bigger than pivot into rightmost value l.t. pivot
    //  result is swapping values about pivot, and ordering at least two values
    arr[high]=low_vac;        
    if (global_flag) {
      cout << " Array after this iteration in partition:\n";
      print(arr,global_n);
      cout << "Boundaries:" << low << "," << high << endl;
    }
  }
  if (global_flag)
    cout << "Array Partitioned. Pivot index is " << low << endl;
  // Low is now == high:
  //    elts below low are l.t. pivot & elts above low are g.t. pivot
  arr[low]=pivot;               // copy the pivot back into its spot
  return low;                   // return the index of the pivot
}