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:
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...
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:
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?
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.