Why does this go into an infinite loop?

[Neb1000]

I wrote the quick sort function but when I run it it doesn't exit the loop and I don't know where the problem is at. Any help would be greatly appreciated.

quick sort function

template<typename generic>
void quick_sort(vector<generic>& v)
{
	stack<int> front;
	stack<int> back;
	int above, below, index = 1, pivotPt = 0;
	bool swapedPivot = false;
	front.push(0);
	back.push(v.size()-1);
	while(!front.empty())
	{
		pivotPt = front.top();
		index = pivotPt+1;
		if(front.top() < back.top())
		{
			while(!swapedPivot)
			{
				bool done = false;
				index = pivotPt+1;
				while(!done)
				{
					if(index == v.size())
					{
						above = v.size();
						done = true;
					}
					else if(v[index] > v[pivotPt])
					{
						above = index;
						done = true;
					}
					index++;
				}
				done = false;
				while(!done)
				{
					if(above == v.size())
					{
						done = true;
					}
					else if(index == v.size())
					{
						below = v.size();
						done = true;
					}
					else if(v[index] < v[pivotPt])
					{
						below = index;
						done = true;
					}
					index++;
				}
			
                                if(below == v.size() || above == v.size())
				{
					swap(v, above-1, pivotPt);
					back.pop();
					front.pop();
					front.push(pivotPt);
					back.push(above-2);
					front.push(above);
					back.push(v.size()-1);
					swapedPivot = true;
				}
				else
				{
					swap(v, above, below);
				}
			}
		}
		if(front.top() >= back.top())
		{
			front.pop();
			back.pop();
		}
	}
}

My test function in case the problem is there

void Test_library::test_quick_sort()
{
	vector<int> v(TEST_MAX);
	cout << endl << "TEST QUICK SORT" << endl;
	cout << "checking when full: ";
	for(int i = 0; i < TEST_MAX; i++)
	{
		v.push_back(i);
	}
	quick_sort(v);
	for(int i = 0; i < TEST_MAX; i++)
	{
		CPPUNIT_ASSERT(v[i] == i);
	}
	cout << "PASSED" << endl;
}

[simeonz]

First, I get some warnings in GCC, when I compile the code. There are comparisons between signed and unsigned integers. These are ok I think, but you could fix them if you wanted to. They are all related to those size() calls.

I assume that this is not some kind of trinary swap out there, but just function that swaps two elements in some container, where the caller provides the their indexes.

First, let me start with your test, because there is a problem with it.
vector<int> v(TEST_MAX);
The above line will allocate vector with TEST_MAX default initialized elements in it. That is, vector with TEST_MAX zeros in this case.

	for(int i = 0; i < TEST_MAX; i++)
	{
		v.push_back(i);
	}

And this appends sequence of natural numbers after the zeros one by one, enlarging the vector at each step. The result is a vector with TEST_MAX * 2 elements, starting with TEST_MAX zeros, and ending with ascending sequence of TEST_MAX integers. Looking at your test condition, I would say that this is not what you intended. May I suggest that you construct your test data this way instead:

    vector<int> v(TEST_MAX);
    cout << endl << "TEST QUICK SORT" << endl;
    cout << "checking when full: ";
    for(int i = 0; i < (int)v.size(); i++)
    {
        v[i] = i;
    }
    random_shuffle(v.begin(), v.end());

Basically, I fill a vector with the first TEST_MAX natural numbers. Then I shuffle them randomly. You can not control the seed for the randomization this way, but you can supply custom randomizer to random_shuffle, and then you will have full control. See
http://www.cplusplus.com/reference/algorithm/random_shuffle/

Next, regarding your code. You want to create quicksort without recursion I see :) The partitioning is at fault.

First, there are two kinds of partitioning algorithms that I know:
- one uses a non-circular crawling (or what's it called) queue that stores the current build for the second partition
- one that travels simultaneously from both directions and swaps elements that are inverted with respect to the pivot (the element towards the end is smaller than the pivot and the element towards the beginning is greater then the pivot)

Looking at your code, I assume that you are going for the second variant. The problem is that you don't traverse simultaneously from both directions. You start looking for the element that is out-of-place from below and then instead of starting to look for the element that is out of place from above, going in the reverse direction, you pick up from where the search left you and continue in the same direction. You should be doing ++index first, and then --index.

Respectively, this line is incorrect:
if(below == v.size() || above == v.size())
because the idea is not to reach the end with both pointers, but to have them meet or cross each other. That is below >= above or smth like that.

You should also remember not to start searching for the next pair to swap from the ends every time. After you swap a pair of inverted elements you continue searching towards the "middle" starting from the locations of the last swap (not from both ends again). Otherwise the quicksort will not be very quick.

Another issue is that those lines are incorrect:

					if(index == v.size())
					if(above == v.size())
					else if(index == v.size())
					back.push(v.size()-1);

The problem is that the end of the vector is not the end of the current partitioning task. The end is held in back.top(), remember? So you should pull it from there, instead of looking at v.size() - 1 in those conditions.

Try to fix those things and see if it works. Ask questions if something is not clear.

Regards

[Neb1000]

Ok I think I might understand what you are saying. But the way my teacher wants us to do it the way I have, even though your way is faster. I have gone through it with pencil and paper a few times looking at every step and it should work but it gets stuck in an endless loop when I run it, but when I step through it it should exit all the loops.

[firedraco]

Try using a debugger and looking at the values as you run it. It'll also help you figure out which loop you get stuck in.

[Neb1000]

When I try to compile where I can use a debugger I get unresolved externals error and I really don't have time to try and figure that out right but I wish I could. :(

[cbeginplusplus]

Just a quick glance over so take it with a grain of salt.

Line 63 states swapedPivot = true permanently disabling future access to the while loop.
Line 71 can be replaced with else.

[Neb1000]

Yes it was that I never reset swapedPivot back to false. Now I feel like an idiot for taking all that time just for that.

[simeonz]

cbeginplusplus is right. I actually had recoded the whole thing and entirely forgot about the swapedPivot = true part. The most amazing thing is, it works. It passed a lot of random tests. And I guess, you are taught that this is the way to do quicksort. Come on...

EDIT: Forget about it. The important thing is that cbeginplusplus found the problem. quicksort or no quicksort, it sorts ;)