CODEWITHSUNDEEP
c++algorithmquicksort
zaidjan1295
zaidjan1295

Reputation: 39

quicksort implementation that returns original values

so i tried to implement the quicksort algorithm but heres the thing, as i followed the code in a debugger at a point all the elements were in sorted order however, this algorithm undid everything in some three recursive call that followed after the elements were sorted. please tell me whats going wrongs

#include <iostream>
#include <vector>

using namespace std;

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

void quicksort(vector<int> A, int start, int end)
{
    if (start < end)
    {
        int pivot = A[start];
        int i, j = start;
        for (i = start + 1;i < end;i++)
        {
            if (pivot>A[i])
            {
                swap(A[i], A[j + 1]);
                j++;
            }
        }
        swap(A[start], A[j]);
        quicksort(A, start, j - 1);
        quicksort(A, j + 1, end);
    }
}

int main()
{
    vector<int> A = { 2,8,7,1,3,5,6,4 };

    quicksort(A, 0, A.size());

    for (int i = 0; i < A.size(); i++)
        cout << A[i] << endl;

    return 0;
}

Upvotes: 1

Views: 66

Answers (2)

Peter
Peter

Reputation: 109

After a quick look, i spotted the following :

You need to pass the vector as a reference. Remember that the lifespan of a variable inside quicksort is only temporary(until the function ends). 

void quicksort(vector<int>& A, int start, int end)

I also changed 

quicksort(A, start, j -1 );
quicksort(A, j + 1, end);

to

quicksort(A, start, j );
quicksort(A, j + 1, end);

because you seemed to skip A[j]. I think it works now. Your main issue was passing the vector by reference.

Upvotes: 0

molbdnilo
molbdnilo

Reputation: 66451

You're passing a copy of the vector to the function.

You need a reference parameter, like you did with swap:

void quicksort(vector<int>& A, int start, int end)

(By the way, swap is in the standard library.)

Upvotes: 6

Related Questions