I was trying to implement QuickSort but getting garbage array elements as output

Question

This is my partition logic for quick sort, and it is providing me Garbage array element values as error. I think I am mistaken with my partition code but also i am not sure about that.

#include <bits/stdc++.h>
using namespace std;

void swap(int* x, int* y)
{

    int temp = *y;
    *y = *x;
    *x = temp;
}

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

void quickSort(int* A, int left, int right)
{

    if (left >= right)
        return;
    int pi = partition(A, left, right);
    quickSort(A, left, pi - 1);
    quickSort(A, pi + 1, right);
}

int main()
{

    int A[] = { 5, 8, 1, 31, 2, 44, 6, 0, 8, 4 };
    int n = sizeof(A) / sizeof(A[0]);
    quickSort(A, 0, n - 1);
    for (auto i : A)
        cout << i << " ";
    return 0;
}

This seems like a good time to learn how to use a *debugger* to step through your code statement by statement while monitoring variables and their values. — Some programmer dude, Mar 04 '21 at 07:14
Please provide a [mre]. Why are you passing pointers to `std::swap`? — Alan Birtles, Mar 04 '21 at 07:21

score 1 · Answer 1 · answered Mar 04 '21 at 08:32

In your while loop you are using 3 separate if statements. All 3 will be potentially executed on every iteration before checking than i <= j. In the second call to partition this results in j being set to -1, from this point on your code writes lots of values out of bounds of the array causing stack corruption and a crash or at least an incorrect result.

Adding else solves the problem:

while (i <= j) {
    if (A[i] <= pivot)
        ++i;
    else if (A[j] > pivot)
        --j;
    else if (A[i] > pivot && A[j] <= pivot) {
        swap(&A[i], &A[j]);
        ++i;
        --j;
    }
}

Note that choosing the first element as the pivot results in worst case performance for quick sort when the array is already sorted, generally the mid point is a better choice.

Unrelated to your problem but see also:

Why should I not #include <bits/stdc++.h>?

Why is "using namespace std;" considered bad practice?

Having a function with the same name as a function in the standard library (swap) combined with importing the whole of the standard library via bits/stdc++.h and bringing the whole standard library into the global namespace via using namespace std is likely to lead to ambiguous overload errors.

thanks a lot Alan, I saw your profile you are a C++ Developer and that's too good. I also want to be a C++ Developer could you please help me by providing some suggestions about which technologies i should learn and which features I must learn to be a developer. — Desh Deepak Mishra, Mar 04 '21 at 13:03
Learning to use a debugger is a key skill for any programmer — Alan Birtles, Mar 04 '21 at 13:57

I was trying to implement QuickSort but getting garbage array elements as output

1 Answers1