quicksort following the algorithm of "Introduction to Algorithms"

qsort.cpp

#include <iostream>

using namespace std;

int partition(int array[], int lo, int hi)
{
    // pivot=A[hi]; A[i] < pivot; A[j] >= pivot
    int i = lo-1;
    int j = lo;
    for (j = 0; j < hi; ++j) {
        if (array[j] < array[hi]) {
            i++;
            swap(array[i], array[j]);
        }
    }
    i++;
    swap(array[i], array[hi]);
    return i;
}

void qsort(int array[], int lo, int hi)
{
    if (lo < hi) {
        int mid = partition(array, lo, hi);
        qsort(array, lo, mid-1);
        qsort(array, mid+1, hi);
    }
}

void print_array(int array[], int len)
{
    int i;
    for (i = 0; i < len; ++i) {
        cout << array[i] << " ";
    }
    cout << endl;
}

int main(int argc, char *argv[])
{
    int A[] = {1,3,2,5,1,2,3,5};
    int len = sizeof(A)/sizeof(A[0]);
    print_array(A, len);
    qsort(A, 0, len-1);
    print_array(A, len);
    return 0;
}