Passing by reference issue

[Hephaestus1233]

So I am attempting to make a sorting program using the QuickSort method. However I am passing a vector by reference I think it is that that is messing my results up.
Code:

void sort(std::vector<int> &vec){
    using namespace std;
    vector<int> temp = vec;
    vector<int> last; // last sortation
    for (int j = 0; j < (size * 10); j++){
        int piv = temp[(std::rand() % size)];
        vector<int> fPiv; //infront of piv
        int fIndex = 0;
        vector<int> sorted;

        for (int i = 0; i < size; i++){
            if (temp[i] != piv){
                if (temp[i] <= piv){
                    sorted.push_back(temp[i]);
                }else if (temp[i] > piv){
                    fPiv.push_back(temp[i]);
                    fIndex++;
                }
            }
        }
        sorted.push_back(piv);
        for (int i=0; i< fIndex; i++){
            sorted.push_back(fPiv[i]);
        }
        last = temp;
        temp = sorted;
    }
    vec = temp;
}

Outputs are first the unsorted and then the sorted:

1:
{0,0,0,2,2,0,0,0,0,1}
{0,1,2,2,2,2,2,0,0,1}

2:
{1,0,0,4,3,1,0,2,3,4}
{0,1,2,3,4,1,0,2,3,4}

3:
{1,1,2,3,1,2,4,3,1,1}
{1,2,3,4,1,2,4,3,1,1}

The problem I think is the passing by reference of the vector. Sometimes some numbers will multiply and remove the others. Like I start with one 4 and then it becomes four 4s in the sorted. And I don't really know what is happening. It could be because I am not using 'new' and 'delete' but I really don't know past the reference thingy...

[tpb]

References have nothing to do with it.

Firstly, you're going to have to call that a "slow quick sort". You're just doing a bunch of first-level partitions with randomly-chosen pivots. That's not a proper quick sort at all. Quick sort puts the pivot element into its final position creating two sub-arrays, then the two sub-arrays are recursively sorted (or possibly an iterative solution using a stack would be an optimization).

Your if (temp[i] != piv){ condition is incorrect. You can't just ignore duplicates of the pivot. You'll need to use the actual index of the pivot to protect it from being copied twice.

So your (not quick) sort would look something like this:

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>

void sort(std::vector<int> &vec) {
    int size = vec.size();
    for (int j = 0; j < 10*size; j++) {
        int piv = std::rand() % size;
        std::vector<int> lower, higher;
        for (int i = 0; i < size; i++) {
            if (i == piv) continue;
            if (vec[i] <= vec[piv])
                lower.push_back(vec[i]);
            else
                higher.push_back(vec[i]);
        }
        lower.push_back(vec[piv]);
        for (int i = 0; i < int(higher.size()); i++)
            lower.push_back(higher[i]);
        vec = lower;
    }
}

int main() {
    std::srand(std::time(0));
    std::vector<int> v{6, 2, 4, 9, 7, 0, 3, 5, 1, 8, 6, 2, 9};
    for (auto x: v) std::cout << x << ' '; std::cout << '\n';
    sort(v);
    for (auto x: v) std::cout << x << ' '; std::cout << '\n';
}

The other nice thing about a real quick sort is that it is done in place. It doesn't need all of that copying of the array.

[Hephaestus1233]

So my issue was that I was ignoring the values that were the same as my pivot, and I was sorting the pivot itself which made a copy when I re-added the pivot. Thanks for pointing that out.

Also, using a stack while iterating over it would make my algorithm a "proper" quick sort algorithm? Like how would I make it an actual "quick" sort?

[tpb]

I personally wouldn't use a stack. I would just code it recursively. Using a stack would be a way of removing the recursion if one were so inclined.

You've coded a partition (which is part of a quick sort) but you haven't coded a quick sort. You only ever partition the whole array. Quicksort is a divide-and-conquer algorithm. It divides the array into two parts: those lower/equal than the pivot, those higher than the pivot (and the pivot in between them). Then those smaller parts are separately (recursively) sorted.