QuickSort with Templates, stack overflow error. NULL ptr?

[Jorge626]

I am trying to implement the quick sort algorithm but I run into a stack overflow error. I can't figure out what's wrong with it, I think it might have to do with my typenames/typedefs, but I'm not sure. Here is my function

int partition(Vect &values, int left, int right) {
	int pivotIndex = right;
	K pivotValue = values[pivotIndex].key();
	int i = left, j = right;
	K temp;
	while (i <= j) {
		while (!keyComparator(values[i].key(), pivotValue)) {
			i++;
		}
		while (keyComparator(values[j].key(), pivotValue)) {
			j--;
		}
		if (i <= j) {
			temp = values[i].key();
			values[i].setKey(values[j].key());
			values[j].setKey(temp);
			i++;
			j--;
		}
	}
	return i;
}

void quickSort(Vect &values, int left, int right) {
	if (left < right) {
		int pivotIndex = partition(values, left, right);
		quickSort(values, left, pivotIndex - 1);
		quickSort(values, pivotIndex, right);
	}
}

This is the keyComparator function

bool keyComparator(K a, K b) { return a > b; }

These are my typename/tyepdefs

template <typename K, typename V>
class Sorting {
public:
	typedef Entry<K, V> E;
	typedef std::vector<E> Vect;
	Vect vList;

Entry is a class that holds a key value pair.

And this is how I am declaring it in main()

myVect.quickSort(myVect.vList, 0, myVect.vList.size() - 1);

I have to implement it with two different pivots, one with the last element as the pivot and another with the median of three as a pivot, I am using the last element as the pivot here. Any help will be greatly appreciated!

[TheToaster]

An easy way to check what's going on is to check the value of pivotIndex every time and see if the condition left < right is met before the stack overflow occurs.

[Jorge626]

I'm working with a vector with 1000 values, after about the 10th iteration the pivotIndex remains 9 and that is when the stack overflow occurs. The condition is never met because left remains at 1 and right remains at 9. I noticed that once it reaches that point, right before the iteration where it starts to overflow, it calls my second quickSort on line 28, with the pivot index being 1 and right being 9. After this it continues the loop that's causing the stack overflow. But I am not sure why left is not updating?

[salem c]

> I'm working with a vector with 1000 values, after about the 10th iteration the pivotIndex
> remains 9 and that is when the stack overflow occurs.
How do you know whether it's the "stuck at 9" is causing endless recursion, or the fact that you have multiple nested instances of what might be a very large object stored in each stack frame, and 9 just happens to be where your luck runs out.

Can you see the stack trace when it bombs?
- If you see multiple identical frames where int left, int right are the same, then it would seem to be a logic problem.
- But if every frame is different, then you just ran out of stack because your stack demands are excessive.

> K pivotValue = values[pivotIndex].key();
> K temp;
..
> bool keyComparator(K a, K b) { return a > b; }
How big is K?

[Jorge626]

@salem c
Hmm I'm not so sure... I assumed that was the problem because at the end of my partition function, when I return i, all of my variables are always the same. So I just assumed that I was in an endless recursion. I didn't think of it to be just because of a large object. If that was the case how can I make sure that I don't have a very large object? None of my values should be that large, they're all in a range from 0 - 999... or am I not thinking of your question correctly?

When looking at the stack trace, I do have multiple instances where int left and right are the same. So I am guessing I have a logic error on my hands?

For temp, it never gets assigned a value during the endless recursion because

if (i <= j) 

never runs, as for pivotValue, it remains 99 inside the endless recursion. When looking into the file with all the values, there is only one instance where I have 99. It should be the second to last value in my vector

[helios]

There's multiple problems here.
1. The way you're choosing your pivot, your code will generally cause a stack overflow if you're passed a sorted vector.
2. Your partitioning algorithm is incorrect. You initialize both j and pivotIndex to 'right', but you swap v[i] and v[j], so the first time there's a swap you send the pivot value to some random location in the vector and you send v[i] to the back:
[..., v[i], ..., v[pivotIndex]] -> [..., v[pivotIndex], ..., v[i]]
When in reality this is what should happen:
[..., v[i], ..., v[pivotIndex - 1], v[pivotIndex]] -> [..., v[pivotIndex], ..., v[pivotIndex - 1], v[i]]
3. You never move pivotIndex after swapping.

[dhayden]

You're also swapping the keys in Vect, but not the values. So it's getting all messed up.

[Jorge626]

@helios
Unfortunately, for my assignment I have to use the last value as my pivot. I know that it is not recommended, but my professor wants us to use it as a test case. I have to use 2 different pivots and compare them, one with the median of three as my pivot, and another as the last value as my pivot.

I tried to use the median of three as my pivot and I ran into the same problem. Does that still not help the problem you described in 2? You mentioned that I have to swap my pivot index instead of j, but I thought that the pivot index is used only to start the recursion? I thought i and j are what keeps track of the values less than my pivot and swaps them, then at the end it returns i, which should be the index where my next pivot for my next recursion should be, right? Or is the way that I am thinking about the algorithm incorrect? As for 3, I am confused as to when I am supposed to do that. After what you mentioned in 2, I believe that I should have done that right before I return i, but that didn't help. So the way I am doing the swapping with i and j is the problem?

@dhayden
Thank you for pointing that out! I fixed it to include the values as well

[ne555]

in your partition() if you have a sorted section, 'i' may go over 'right' and 'j' may go under 'left'
so the function ends up returning 'right+1' and you get stuck in the same recursion over and over again

> I'm working with a vector with 1000 values
surely, you could reproduce the issue with a smaller vector
be concious when testing, like cases where the vector is sorted, reversed, all elements are equal, empty vector and so on
don't just try once with random values and be done

> I run into a stack overflow error.
> I think it might have to do with my typenames/typedefs,
that's like saying: my car doesn't start, perhsaps it's because its colour