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;
    }

In my last post i share the c++ example, don't consider it, for C, i am sharing a reference, read this: cquestions.com/2008/01/c-program-for-quick-sort.html — devpro
for (j = l+1; j < len; j++) looks wrong. What if l is 7 and r is something like 12? len is 6 but j starts at 8. The for loop will never run. — Millie Smith

vish4071 vish4071 · Accepted Answer · 2015-12-23T06:50:45

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;
}

Quicksort implementation in C using first element as pivot

2 Answers