#include <iostream>
using namespace std;

void SWAP(int arr[], int& first, int& sec)
{
   int temp = arr[first];
   arr[first] = arr[sec];
   arr[sec]=temp;
}

// This is the INPLACE partition used by the QuickSort Algorithm.
//  If an elt larger than the pivot is found on the left of the array and an elt smaller than the pivot is found at the right of the array, the elements are swapped.

int partition(int A[], int beg, int end )
{
     int low, high;
     int pivot_item, pivot;
     pivot_item = A[beg];       // we use the first elt in the array as the 'pivot'
     pivot = low = beg;            // 'pivot' stores the index or location of the pivot_item in the array
     high = end;                       // initialize low to the beginning of the array and high to the end of the array

     while ( low < high ) {
     	/* Move low while item < pivot */
     	while( A[low] <= pivot_item ) 
		low++;
        /* Move high while item > pivot */
        while( A[high] > pivot_item ) 
		high--;
        if ( low < high ) 
		SWAP(A,low,high);
     }
     /* high is final position for the pivot */
     A[beg] = A[high];
     A[high] = pivot_item;
     return high;                                // new position for the pivot is returned
}


int main()
{
     int arr[10]={11, 6, 9, 3, 7, 2, 1, 8, 5, 10};
     cout << "Index of elt 0:" << arr[0] << " is: ";
     int index=partition(arr, 0, 9);
     cout << index << endl;
     return 0;
}