#include <iostream>
#include <cstdlib>

using namespace std;
#define max_size 20

int partition(int a[], int start, int end){
  int i,j,pivot,temp;

  pivot = a[end]; //select last elem as the pivot
  i = start- 1;   // point i and j to before/after start end of the arr
  j= end +1;
  
  while(true){
    //reduce j until we reach an elem that is less than pivot
  	if(a[j] >= pivot){ j= j-1; }	
    //increase i until we reach an elem that is more than pivot
	if(a[i] <= pivot){ i = i+1; }  
	
	
	if(i<j){  //swap elems so that it is partitioned
		  temp = a[j];
		  a[j] = a[i];
		  a[i] = temp;
    }
    else{ return j; } //return the boundary for this partition
  }
}

void quick_sort(int arr[], int start, int end){
   int boundary;
   if(start<end){
		 boundary = partition(arr,start,end);
		 
		 quick_sort(arr,start,boundary);
   		 quick_sort(arr,boundary+1, end);
   }
   return;
}

int main(){
     int n,i;
	 
	 cout << "Please enter array elements size to sort" << endl;
	 cin >> n;
	 
	 int a[n];

	 cout << endl <<  "Please enter array of size " << n << endl;
		  	 
	 for(i=0;i<n;i++){
       	cin >> a[i];		  
     }
	 
	 cout << endl <<  "the array before sorting is: " << endl;
	 
	  for(i=0;i<n;i++){
        cout << a[i] << "\t";
      }	
	  
	  
	  /* quick sort */
  	  quick_sort(a,1,n);
	  
	  cout << endl <<  "the array after sorting is: " << endl;
	  
      for(i=0;i<n;i++){
        cout << a[i] << "\t";
      }	 
	 	
	 system("pause");
	 return 0;
}