3
\$\begingroup\$

As an exercise, I've written quicksort algorithm in C using pointers. Please comment and help me find the cases where it breaks (if any).

void qsort(int *, int, int);
void swap(int *, int *);

void qsort(int *v, int left, int right)
{
    int i, *last;

    if (right <= left)
        return;
    last = v + left; //choosing the first element as the pivot
    for (i = left + 1; i <= right; i++)
        if (*(v + i) < *(v + left))
            swap(++last, v + i); //swapping the numbers < pivot
    swap(v + left, last);
    qsort(v, left, last - v - 1); //sub-array containing numbers < pivot
    qsort(v, last - v + 1, right); //sub-array containing numbers >= pivot
}

void swap(int *i, int *j)
{
    int temp;

    temp = *i;
    *i = *j;
    *j = temp;
}
\$\endgroup\$
2
\$\begingroup\$

I'd make right an exclusive instead of inclusive upper bound, that is write i < right instead of i <= right and last - v instead of last - v - 1.

This has the advantage of making the base call qsort(v, 0, length) instead of qsort(v, 0, length - 1).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.