QuickSelect returning random value

[Jorge626]

I am trying to implement a quickSelect algorithm from my textbook. When I set breakpoints and I check all my return parameters, it shows the correct value that should be returned, but when it does return to my main function, it returns a complete different value that was not in my vector to even begin with. I am not sure what's wrong with it, can someone please help?

quickSelect function:

int quickSelect(std::vector<int> vect, int k)
{
	if (vect.size() == 1)
		return vect[0];
	int x = vect[vect.size() / 2];
	std::vector<int> L, E, G;
	for (int i = 0; i < vect.size(); i++)
	{
		if (vect[i] > x)
			G.push_back(vect[i]);
		else if (vect[i] == x)
			E.push_back(vect[i]);
		else
			L.push_back(vect[i]);
	}
	if (k <= L.size())
		quickSelect(L, k);
	else if (k <= L.size() + E.size())
		return x;
	else
		quickSelect(G, k - L.size() - E.size());
}

main function:

int main()
{
	std::cout << "K'th smallest value\n~~~~~~~~~~~~~~~~~~~~\n";
	std::vector<int> vect;
	for (int i = 0; i < 10; i++)
		vect.push_back(i);
	int k = 1;
	std::cout << "k(1): " << quickSelect(vect, k);

	std::cout << "\n";
	return 0;
}

Edit: When using the c++ shell here, it seems to give the correct value, but when I run it on visual studios it does not. Is it something to do with the compiler?

[jonnin]

Print the values and indexes until you spot the bug, or switch your [] to .at() which enforces safety.

[Jorge626]

@jonnin
I printed the values and indexes as you said and everything seems to be returning the expected values, as well as in my return statements. I guess I can just make it into a void function and just have it print out the value, but I still want to figure out why it's not returning the int it should be returning. I get the feeling it might be returning the memory address and not the value? Because it's different after every run. Also, using .at() seemed to not have any change

[jonnin]

it returns vect[0], or x. x is based off the size, vect is the data. This is nonsense to me, making it hard to answer your question.

it does not do anything with addresses or pointers at all.

at should do the same thing, it just will not let you go out of bounds. It will throw if you did, so that means its not going out of bounds, which is good. [] going out of bounds is like an array and may just give you a bogus value and 'work' with bad answers.

[dhayden]

If you turn on warnings, the compiler will tell you what the problem is:

foo.cxx:25:1: warning: control reaches end of non-void function [-Wreturn-type]
 }

	if (k <= L.size())
		return quickSelect(L, k);
	else if (k <= L.size() + E.size())
		return x;
	else
		return quickSelect(G, k - L.size() - E.size());

[Jorge626]

@jonnin
So is the way I am going about it bad practice? The reason I am using the size is so that I could use the middle value of my vector as the pivot point, I suppose I could just use the start of the vector as my pivot, but that will result in more comparisons in the case where I am using a vector that is already sorted like in my example. Also, is returning the vector data bad? I am trying to find and return a value from the vector, so how should I go about returning that value? I thought that returning the data straight from the vector was okay since the data from the vector is an int and my return type is an int.

@dhayden
Thank you! That seemed to have fixed it. I wasn't aware that when using recursion you had to return the function! I mostly worked with void recursions in the past, so I did not think too much about it! But that makes sense now, thank you!