quicksort stack size

Why do we prefer to sort the smaller partition of a file and push the larger one on stack after partitioning for quicksort(non-recursive implementation)? Doing this reduces the space complexity of quicksort O(log n) for random files. Could 开发者_运维百科someone elaborate it?

As you know, at each recursive step, you partition an array. Push the larger part on the stack, continue working on the smaller part.

Because the one you carry on working with is the smaller one, it is at most half the size of the one you were working with before. So for each range we push on the stack, we halve the size of the range we're working with.

That means we can't push more than log n ranges onto the stack before the range we're working with hits size 1 (and therefore is sorted). This bounds the amount of stack we need to complete the first descent.

When we start processing the "big parts", each "big part" B(k) is bigger than the "small part" S(k) produced at the same time, so we might need more stack to handle B(k) than we needed to handle S(k). But B(k) is still smaller than the previous "small part", S(k-1) and once we're processing B(k), we've taken it back off the stack, which therefore is one item smaller than when we processed S(k), and the same size as when we processed S(k-1). So we still have our bound.

Suppose we did it the other way around - push the small part and continue working with the large part. Then in the pathologically nasty case, we'd push a size 1 range on the stack each time, and continue working with a size only 2 smaller than the previous size. Hence we'd need n / 2 slots in our stack.

Consider the worst case where you partition in such a way that your partition is 1:n. If you sort small subfile first than you only need to use O(1) space, as you push the large subfile and then pop it back (and then again push the large subfile). But, if you sort large subfile first than you need O(N) space, because you keep pushing 1 element array in the stack.

Here is a quote from Algorithms by ROBERT SEDGEWICK (he was the one who wrote paper on this) :

For Quicksort, the combination of end- recursion removal and a policy of processing the smaller of the two subfiles first turns out to ensure that the stack need only contain room for about, lg N entries, since each entry on the stack after the top one must represent a subfile less than half the size of the previous entry.

OK, am I right that you mean if we make the Quicksort algorithm non-recursive, you have to use a stack where you put partitions on the stack?

If so: an algorithm must allocate for each variable it uses memory. So, if you run two instances of it parallel, they are allocating the double amount of one algorithm memory space...

Now, in a recursive version, you start a new instance of the algorithm (which needs to allocate memory) BUT the instance which calls the recursive one, DOES NOT end, so the allocated memory is needed! -> in fact, we have started lets say 10 recursive instances and need 10*X memory, where X is the memory needed by one instance.

Now, we use the non-recursive algorithm. You MUST only allocate the needed memory ONCE. In fact, helper variables only use the space of one instance. To accomplish the function of the algorithm we must save the already made partitions (or what we haven't done already). In fact, we put it on a stack and take the partitions off until we made the last "recursion" step. So, imagine: you are giving the algorithm an array. The recursive algorithm needs to allocate the whole array and some helper variables with each instance (again: if the recursion depth is 10, we need 10*X memory where the array needs much). The non-recursive one needs to allocate the array, helper variables only once BUT it needs a stack. However, in the end you won't put so many parts on the stack that the recursive algorithm will need less memory due to the part that we doesn't need to allocate the array again each time/instance.

I hope, I have described it so that you can understand it, but my English isn't soooo good. :)