// quiksort.cpp

#include <iostream.h>

// to turn trace on, change 0 to 1 in #define statement
// this method can also be used to debug code without having to
// comment out all debugging statements later

#define TRACE 0

void Swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
}

void Pivot(int a[], int left, int right){
    if (a[left] > a[right]){
        Swap(a[left], a[right]);
	if (TRACE)
	    cout << "pivot swap " << a[left] << " " << a[right] << endl;
    }
}

int Partition(int a[], int left, int right){
    int pivot = a[left];
    int i = left;
    int j = right+1;
    
    if(TRACE)
        cout <<"pivot = "<<a[left]<<" i = "<<i<< " j = " << j << endl; 
    do{
	do{
	    ++i;
        }while(a[i] < pivot);
        if (TRACE)
	    cout << " i = " << i << endl;
        do{
	    --j;
	}while(a[j] > pivot);
	if(TRACE)
	    cout << " j = " << j << endl;
	if (i < j){
	    Swap(a[i], a[j]);
            if(TRACE)
	        cout << "part swap " << a[i] << " " << a[j] << endl;
	}
    }while (i < j);
    Swap(a[j], a[left]);
    if (TRACE)
        cout << "p swap " << a[j] << " " << a[left] << endl;
    return j;
}

void printarray(int a[], int first, int last){
    for (int i = first; i <= last; i++)
	cout << a[i] << "  ";
    cout << endl;
}

void quicksort(int array[], int left, int right){
    if (left < right){
	Pivot(array, left, right);
        if(TRACE)
	    printarray(array, left, right);
        int k = Partition(array, left, right);
	if(TRACE){
	    cout << "k = " << k << endl;
	    printarray(array, left, right);
	    cout<<"quicksort(array,"<<left<<","<<k-1<< ")"<<endl;
 	}
	quicksort (array, left, k-1);
        if(TRACE){
	    printarray(array, left, k-1);
	    cout<<"quicksort(array,"<<k+1<< "," <<right<< ")" << endl;
	}
	quicksort (array, k+1, right);
	if(TRACE)
	    printarray(array, k+1, right);
    }
}

int main(){
    int a[7] = {5,8,2,9,1,4,7};

    printarray(a,0,6);
    quicksort(a,0,6);
    printarray(a,0,6);

    return 0;
}