Quicksort implementation in C using first element as pivot

Question

I am a complete beginner to stackoverflow and this is my first post. Please forgive if this is not the correct place to post these kinds of queries. I have written code for the Quicksort algorithm, based on the algorithm given in the Algorithms course in Coursera(It is not for any assignments though).

Basically, there are two functions Quicksort which is called recursively and partition() function that returns the index of the pivot. I select the pivot as the first element of the array every time. I checked the partition() function and it works fine but the array is not sorted even after I call the Quicksort() function.

Any help is appreciated. Thanks.

    #include <stdio.h>
    void swap(int *p, int i, int j)
    {
        int temp = *(p+i);
        *(p+i) = *(p+j);
        *(p+j) = temp;
    }

    int partition(int *q, int l, int r)
    {
        int i = l+1, j;
        int p = l;
        int len  = r-l +1;
        for (j = l+1; j < len; j++)
        {
            /*printf("%d \n", j);*/
            if ( *(q+j) < *(q+p) )
            {
                swap(q, i, j);
                i += 1;
            }
        }
        swap(q, l, i-1);
        /*printf("%d", i-1);*/
        return (i-1);
    }

    void quicksort(int *ptr, int low, int high)
    {
        if (low < high)
        {
            int p = partition(ptr, low, high);
            printf("%d\n", p);
            quicksort(ptr, low, p);
            quicksort(ptr, p+1, high);
        }
    }


    int main(){
        int i;
        int a[] = {3, 8, 2, 5, 1, 4, 7, 6};
        int len  = sizeof(a)/sizeof(a[0]);
        for ( i = 0; i < len; ++i)
        {
            printf("%d ", a[i]);
        }
        printf("\n");
        int *ptr = a;
        quicksort(ptr, 0, len-1);
        for (i = 0; i < sizeof(a)/sizeof(a[0]); ++i)
        {
            printf("%d ", a[i]);
        }
        printf("\n");
        return 0;
    }

Answer 1

2 corrections.

Small one: Change 3rd line inside if block in QuickSort function

from

quicksort(ptr, low, p);

to

quicksort(ptr, low, p-1);

This will improve performance.

Main error:

Your partition function is wrong. Specifically the loop where j runs from l+1 to r-l+1, because, r-l+1 can be less than l+1

I'll write the partition function for you if you want (post a comment if you face any problem with that) though I'd advice you to do it yourself.

EDIT:

A possible partition function:

int partition(int *q, int l, int r){
    int i,j;
    int p = *(q + l);
    for(i = l + 1, j = r; ;){
        while(*(q + i) <= p)
            i++;
        while(*(q + j) >= p)
            j--;
        if(i >= j)
            break;
        swap(q, i, j);
    }
    return i;
}

Answer 2

Changes noted in comments.

int partition(int *q, int l, int r)
{
    int i = l+1, j;
    int p = l;
                                    /* fix: int len = r-l+1; is not used */
    for (j = l+1; j <= r; j++)      /* fix: j <= r */
    {
        if ( *(q+j) <= *(q+p) )     /* fix: <= */
        {
            swap(q, i, j);
            i += 1;
        }
    }
    swap(q, l, i-1);
    return (i-1);
}

void quicksort(int *ptr, int low, int high)
{
    if (low < high)
    {
        int p = partition(ptr, low, high);
        quicksort(ptr, low, p-1);   /* optimization: p-1 */
        quicksort(ptr, p+1, high);
    }
}

If interested, Hoare partition scheme is faster. If you switch to this, don't forget to change the two quicksort calls to quicksort(lo, p) and quicksort(p+1, hi) ). You might want to change the Hoare pivot to pivot = A[(lo+hi)/2], which will avoid worst case issue with sorted or reverse sorted array.

http://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme