recursion on returning vectors c++

Question

Hey guys I am trying trying to right this javascript code into c++. I am doing quick sort and everything is straight forward minus the last step.

function quickSort(arr)
{
    //base case if the arr is 1 or 0 then return the array
    if(arr.length === 1 || arr.length === 0)
    {
        return arr;
    }


    var pivotIndex = Math.floor(arr.length/2);
    var pivotValue = arr[pivotIndex];

    var before = [];
    var after = [];

    for(var counter = 0; counter < arr.length; counter++)
    {
        if(counter === pivotIndex)
            continue;
        if(pivotValue <= arr[counter])
        {
            before.push(arr[counter])
        }
        else
        {
            after.push(arr[counter])
        }
    }
//this step I am having trouble rewriting in c++
    return quickSort(after).concat(pivotValue).concat(quickSort(before));

}

I am having a hard time rewriting the recursive step in c++. I am not sure how concat 2 vector. I tried using the insert method but I keep getting an error about invalid use of void expression.

vector<int> quickSort(vector<int> arr)
{
    if(arr.size() == 1 || arr.size()  == 0)
    {
        return  arr;
    }

    int pivotIndex = arr.size()/2;
    int pivotValue = arr[pivotIndex];

    vector<int> before;
    vector<int> after;


    //put values in before or after the piv
    for(size_t counter = 0; counter < arr.size(); counter++)
    {
        if(counter == pivotIndex)
            continue;
        if(pivotValue <= arr[counter])
            before.push_back( arr[counter]);
        else
            after.push_back( arr[counter]);
    }

   return //????? not sure how to do this

}

lol sure thats great I understand that but my c++ is a bit rusty so an example would be nice — user1314272, Aug 08 '17 at 00:32
Concatenate `v` and `v2`: `v.insert(v.end(), v2.begin(), v2.end())`. — Jarod42, Aug 08 '17 at 00:37
It would be more performant to make the partition in place to avoid extra allocations (and so working with *range* instead of *container*). — Jarod42, Aug 08 '17 at 00:40
Step 1: rewrite JS into doing one line per "thing". Step 2: test new code works the same as old code. Step 3: Try to rewite each line of JS in C++. None of these involve "invalid use of a void expression", and you shoukd have *something* besides ??? before asking here. — Yakk - Adam Nevraumont, Aug 08 '17 at 00:53

Clavin · Accepted Answer · 2017-08-08T00:56:08.917

So, you realized that your core question was "how to concatenate two vectors", and you found a right answer: using insert. Now your question is about why you were getting "an error about invalid use of void expression." (That's the assumption my answer is for, at least.)

That's because you were likely trying to do something like the following:

return quickSort(after).insert( /* stuff */ );

which is wrong. In JavaScript, array.concat returns the concatenated array. It's return type is effectively Array, and so doing return arr.concat(arr2) returns an Array because arr.concat would return an Array. Further, in JavaScript, array.concat doesn't modify the array it was called on, but rather returns a new array.

In C++, however, vector.insert (#4 in the reference) returns void. That means it returns nothing. So when you try to return the result of insert, you get that error about invalid use of a void expression. Further, in C++, vector.insert does modify the vector it was called on.

So how do you use insert in this case?

vector<int> quickSort(vector<int> arr)
{
    // ...

    // Sort `before` and `after`
    before = quickSort(before);
    after = quickSort(after);

    // Modify `after` and return it.
    after.push_back(pivotValue);
    after.insert(after.end(), before.begin(), before.end());
    return after;
}

Note: My code isn't optimal and the idea of rewriting JS in C++ is also oddly specific. My answer is to simply outline the problem asked in the question, not to give a good C++ implementation of quick sort.

score 0 · Answer 2 · answered Aug 08 '17 at 00:55

0

To concat two vector , you can use std::merge like:std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(dst));

answered Aug 08 '17 at 00:55

chashao

21
4

recursion on returning vectors c++

2 Answers2