Thread: problem implementing quicksort

Can anyone tell me what's wrong with my quicksort? It seems fine but when i run it seg faults. I've been looking for some time but can't figure out the problem.

Code:

void quicksort(int *a, int start, int end)
{
    if (start < end)
    {
        int p = partition(a, start, end);
        quicksort(a, start, p - 1);
        quicksort(a, p + 1, end);
    }
}

Code:

int partition(int *a, int start, int end)
{
    int x = a[end];
    int pInd = start - 1;
    int i;
    for (i = 0; i < end; i++)
    {
        if (a[i] <= x)
        {
            ++pInd;
            swap(&a[i], &a[pInd]);
        }
    }
    swap(&a[pInd + 1], &a[end]);
    return (pInd + 1);
}

Code:

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;

}

What system are you on? What compiler and debugger are you using?

What line is it segfaulting on? What are the values of the pertinent variables at that point?

BTW, you should post your code in one block, complete with main and headers so that we can copy/paste and run it. To run your code as given I'd have to add stuff to it, which I don't feel like doing.

Sorry about that, here's the code:

Code:

#include <stdio.h>

void quicksort(int *a, int start, int end);
int partition(int *a, int start, int end);
void print_array(int *a, int len);
void swap(int *a, int *b);

int main()
{
    int a[9] = {9, 8, 7, 6, 5, 4, 3, 2, 1};
    print_array(a, 9);
    printf("\n");
    quicksort(a, 0, 8);
    print_array(a, 9);
    return 0;
}

void quicksort(int *a, int start, int end)
{
    if (start < end)
    {
        int p = partition(a, start, end);
        quicksort(a, start, p - 1);
        quicksort(a, p + 1, end);
    }
}

int partition(int *a, int start, int end)
{
    int x = a[end];
    int pInd = start - 1;
    int i;
    for (i = 0; i < end; i++)
    {
        if (a[i] <= x)
        {
            ++pInd;
            swap(&a[i], &a[pInd]);
        }
    }
    swap(&a[pInd + 1], &a[end]);
    return (pInd + 1);
}

void print_array(int *a, int len)
{
    int i;
    for (i = 0; i < len; i++)
    {
        printf("%d ", a[i]);
    }
}

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;

}

Your basic error is in partition where you begin your loop at 0 instead of start.

Also in partition, you could avoid all the -/+ 1's by simply getting rid of all of them and swapping the two lines inside the if.

You could also use a newline at the end since (on linux at least) your program leaves my prompt on the same line as the last line of output. Maybe put the newline in the print routine.