quicksort

quicksort

/* author: Dutor 
 * from : http://www.dutor.net/index.php/2011/04/recursive-iterative-quick-sort/ */

int
partition(int *a, int n) //~ seperate a[], using a[0] as pivot
{
    int l = 0, r = n;
    int pivot = a[l];
    while(l < r)
    {
        while( l < r && a[--r] > pivot) ;
        a[l] = a[r];
        while(l < r && a[++l] < pivot) ;
        a[r] = a[l];
    }
    a[l] = pivot;
    return l; //~ return the final index of pivot
}
void
qsort_recur(int *a, int n)
{
    if(n <= 1)
        return;
    int m = partition(a, n);
    if(m <= n / 2)
    {
        qsort_recur(a, m);
        qsort_recur(a + m + 1, n - m - 1);
    }
    else
    {
        qsort_recur(a + m + 1, n - m - 1);
        qsort_recur(a, m);
    }
}