C++ Quicksort with vectors

Question

The quicksort function works perfectly fine as ive tried it with the standard array. When using vectors however, I get an error message saying swap function doesnt take 3 arguments. Any help would be appreciated.

void quicksort(vector<int> &vec, int L, int R) {
    int i, j, mid, piv;
    i = L;
    j = R;
    mid = L + (R - L) / 2;
    piv = vec[mid];

    while (i<R || j>L) {
        while (vec[i] < piv)
            i++;
        while (vec[j] > piv)
            j--;

        if (i <= j) {
            swap(vec, i, j); //error=swap function doesnt take 3 arguments
                i++;
                j--;
        }
        else {
            if (i < R)
                quicksort(vec, i, R);
            if (j > L)
                quicksort(vec, L, j);
            return;
        }
    }
}

void swap(vector<int> v, int x, int y) { 
    int temp = v[x];
    v[x] = v[y];
    v[y] = temp;

}

int main() {
    vector<int> vec1;
    const int count = 10;

    for (int i = 0; i < count; i++) {
        vec1.push_back(1 + rand() % 100);
    }
    quicksort(vec1, 0, count - 1);

}

Are you saying that i should use offset notation rather subscript notation? — Blake K Akiti, Nov 19 '17 at 22:00
You tried to use your swap function before declaring it. The compiler hasn't seen it yet. Instead, it is looking at `std::swap` from the standard library, which only takes two arguments. You need to declare your functions before trying to use them. — Benjamin Lindley, Nov 19 '17 at 22:02
using namespace std; introduces the std swap function into your namespace and will be declared and defined before your use of your own swap. Move your swap definition higher up and fix the bug where it should be taking the vector by reference rather than by value (copy). — T33C, Nov 19 '17 at 22:04
`using namespace std;`, while of course bad practice, is not at fault here. `std::swap` will be caught by ADL even without it. — Benjamin Lindley, Nov 19 '17 at 22:07
So basically, I had to put the swap function above the quicksort function. and it's now working. Thanks for the help guys. — Blake K Akiti, Nov 19 '17 at 22:09
This question does not demonstrate any research effort (and the sample code is far from minimal (in the sense of [mcve])). — melpomene, Nov 19 '17 at 23:12

score 1 · Answer 1 · edited Nov 20 '17 at 01:06

1

See

void quicksort(vector<int> &vec, int L, int R)

and

void swap(vector<int> v, int x, int y)

The first parameter does not use reference.

edited Nov 20 '17 at 01:06

David G

94,763
41
167
253

answered Nov 19 '17 at 23:43

devin

36
4

score 0 · Answer 2 · answered Nov 20 '17 at 01:18

Like various comment say, problem is that your version of swap is being confused with std::swap. You can fix it by either moving the implementation of swap before you use it or add a declaration before you use it.

Also per Devin's answer, pass by reference so you get the swapped values back.

Here is the fixed code:

#include <vector>
using namespace std;
void swap(vector<int>& v, int x, int y);

void quicksort(vector<int> &vec, int L, int R) {
    int i, j, mid, piv;
    i = L;
    j = R;
    mid = L + (R - L) / 2;
    piv = vec[mid];

    while (i<R || j>L) {
        while (vec[i] < piv)
            i++;
        while (vec[j] > piv)
            j--;

        if (i <= j) {
            swap(vec, i, j); //error=swap function doesnt take 3 arguments
            i++;
            j--;
        }
        else {
            if (i < R)
                quicksort(vec, i, R);
            if (j > L)
                quicksort(vec, L, j);
            return;
        }
    }
}

void swap(vector<int>& v, int x, int y) {
    int temp = v[x];
    v[x] = v[y];
    v[y] = temp;

}

int main() {
    vector<int> vec1;
    const int count = 10;

    for (int i = 0; i < count; i++) {
        vec1.push_back(1 + rand() % 100);
    }
    quicksort(vec1, 0, count - 1);

}

C++ Quicksort with vectors

2 Answers2