C implementation of quick sort produces garbage value at arr[0]

Question

Consider the following algorithm:

void qsort(int arr[], int left, int right) {
        if (left < right) {
        int index = partition(arr, left, right);
        qsort(arr, left, index - 1);
        qsort(arr, index + 1, right);
    }
}

int partition(int arr[], int left, int right) {
    int pivot = arr[right];
    int i = left - 1;
    for (int j = left; j < right; j++) {
        if (arr[j] <= pivot) {
            ++i;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[right]);
    return i + 1;
}

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

After I fixed the segfaults, I noticed that the algorithm always produces a garbage value at arr[0]. So if the input array is: 5 5 1 3 7 0 0 0 3 , the output is -858993460 0 0 0 1 3 3 5 5. I've ran this through a debugger numerous times and nevertheless I still have no idea where the garbage value comes from. What's more interesting is that in Java pretty much the same algorithm works perfectly.

edit The initial function is called like this: qsort(arr, 0, 9); where 9 is the length of the array - 1.

Answer 1

I suspect you have an off-by-one error in how you initialize arr or how you call qsort(). Likely it gets called with a garbage (uninitialized) element either at the start or at the end of the array. This also likely explains why the largest value, 7, is missing from the output.

If I were to speculate further, I'd guess that in Java, the array gets initialized with zeros and so you get an extra zero in the output (that perhaps you're overlooking amongst the other zeros?)

edit: The initial function is called like this: qsort(arr, 0, 9); where 9 is the length of the array - 1.

The 9 is clearly not correct for your example, so here is one error. It would account for the garbage element but not for the missing element.

My next hypothesis is that, having sorted a ten-element array (9 real + 1 garbage) you then only print out the first nine elements. This would account for the missing 7 in your output (it's the largest and so gets placed in the final spot, which is the spot that doesn't get printed out).

P.S. If I may offer some unsolicited advice for future questions, posting a Minimal, Complete, and Verifiable example would make all this debugging-by-conjecture completely unnecessary as we'd be able to see right away what exactly is going on with your code. :)