Need help understanding

[Gamingphreek]

I am asked a series of questions on my homework that I can't comprehend because, in my mind, I don't understand how the algorithm works completel.

Can anyone help me understand how using a stack in a Quicksort algorithm to get rid of recursive calls works?

I understand how a Quicksort works and all its varieties (ie: Median of 3) - but I fail to see how a stack can help function costs.

Thanks,
-Kevin

 

[Crusty]

It really has nothing to do with the sorting algorithm, you are converting a recursive algorithm to an iterative algorithm. Since recursion by nature uses the stack to store the state, using a stack in the iterative function emulates that.

 

[Gamingphreek]

Well I understand the part about converting it to an iterative algorithm and are just creating a stack to emulate the run-time stack - but I just don't understand pushing and popping values from that stack is accomplishing anything.

I found this example online and I, for whatever reason, just can't see whats going on.

static void quicksort(ITEM[] a, int l, int r)
{ intStack S = new intStack(50);
S.push(l); S.push(r);
while (!S.empty())
{
r = S.pop(); l = S.pop();
if (r <= l) continue;
int i = partition(a, l, r);
if (i-l > r-i) { S.push(l); S.push(i-1); }
S.push(i+1); S.push(r);
if (r-i >= i-l) { S.push(l); S.push(i-1); }
}
}

(Yes it is messy in my opinion - I just found it online though)

-Kevin

 

[Ken g6]

Recall that Quicksort partitions a string into two strings, then works on one of them, then the other, recursively. The stack is basically a to-do list of strings to work on. Get a string, split it in two, push each one, then pop one to work on. (Don't forget to stop at some small string length!)

That particular example pushes starts and lengths of strings separately onto the same stack. While this is more or less the way it's done at a low level, it might be better to make a string-position-and-length struct, and push and pop that.

 

[Gamingphreek]

Ok - I think I can see what is going on now. It is essentially emulating the run-time stack which allows the program to run iteratively instead of recursively. That, therefore, then eliminates the function calls and overhead associated with them.

So in the worst case, the maximum number of elements on the stack would be O(n-1) (If the pivot point is bad and the larger stack is sorted first). The best case would involve sorting the smaller string first and then the larger string with a good pivot point which would result in a max of O(log(n)) on the stack at once. Correct?

-Kevin

 

[Ken g6]

You do see what's going on in that first paragraph. But the second sounds like a very specific homework question to me.