// quick.cpp - quicksort demo
// cmc, 5/22/2010

#include <iostream>
using namespace std;

// pass-by-reference function to swap integers
void swap(int &x, int &y) {
    int temp = x;
    x = y;
    y = temp;
}

// partitions portion of integer array for quicksort
void partition(int a[], int &i, int &j) {
    int pivot = a[(i + j) / 2]; // middle element is the pivot

    do {
        // scan i from left, then j from right
        while (a[i] < pivot) i++;   // note:
        while (a[j] > pivot) j--;   // i and j are reference parameters

        // swap if pointers haven't crossed yet
        if (i <= j) {
            swap(a[i], a[j]);
            i++;
            j--;
        }
    }while(i <= j);  // keep scanning until pointers cross
}

// recursive quick sort for integer array
void quicksort(int a[], int left, int right) {
    int i, j;

    if (left < right) {
        i = left; j = right;
        partition(a, i, j);
        quicksort(a, left, j);
        quicksort(a, i, right);
    }
}

// first call just passes whole array to quicksort
void sort(int a[], int n) {
    quicksort(a, 0, n-1);
}

// utility print function for integer array
void pr(int a[], int n) {
    for (int i=0; i<n; i++)
        cout << " " << a[i];
    cout << endl;
}

// simple main
int main() {
    int x[] = {72, 91, 4, 13, 7, 6, 50, 25, 44, 1};
    int n = 10;
    cout << "before sorting:";
    pr(x,n);
    sort(x,n);
    cout << "after sorting:";
    pr(x,n);
    return 0;
}