StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<blockquote> <p>The policy of putting the larger of the small subfiles on the stack ensures that each entry on the stack is no more than one-half of the size of the one below it,</p> </blockquote> <p>That is not quite true. Consider you want to sort a 100-element array, and the first pivot goes right in the middle. Then you have a stack</p> <pre><code>49 50 </code></pre> <p>then you pop the 49-element part off the stack, partition, and push the two parts on the stack. Let's say the choice of pivot was not quite as good this time, there were 20 elements not larger than the pivot. Then you'd get the stack</p> <pre><code>20 28 50 </code></pre> <p>and each stack entry is more than half of the one below.</p> <p>But that cannot continue forever, and we have</p> <blockquote> <p>During the entire sorting, if stack level <code>k</code> is occupied, its size is at most <code>total_size / (2^k)</code>.</p> </blockquote> <p>That is obviously true when the sorting begins, since then there is only one element on the stack, at level 0, which is the entire array of size <code>total_size</code>.</p> <p>Now, assume the stated property holds on entering the loop (<code>while(!stack.empty())</code>).</p> <p>A subarray of length <code>s</code> is popped from stack level <code>m</code>. If <code>s <= 1</code>, nothing else is done before the next loop iteration, and the invariant continues to hold. Otherwise, if <code>s >= 2</code>, After partitioning that, there are two new subarrays to be pushed on the stack, with <code>s-1</code> elements together. The smaller of those two then has a size <code>smaller_size <= (s-1)/2</code>, and the larger has a size <code>larger_size <= s-1</code>. Stack level <code>m</code> will be occupied by the larger of the two, and we have</p> <pre><code>larger_size <= s-1 < s <= total_size / (2^m) smaller_size <= (s-1)/2 < s/2 <= total_size / (2^(m+1)) </code></pre> <p>for the stack levels <code>m</code> resp. <code>m+1</code> at the end of the loop body. The invariant holds for the next iteration.</p> <p>Since at most one subarray of size 0 is ever on the stack (it is then immediately popped off in the next iteration), there are never more than <code>lg total_size + 1</code> stack levels occupied.</p> <p>Regarding</p> <blockquote> <p>What does author mean by "Without end-recursion removal, we cannot guarantee that the stack size will be small for quicksort" ?</p> </blockquote> <p>In a recursive implementation, you can have deep recursion, and when the stack frame is not reused for the end-call, you may need linear stack space. Consider a stupid pivot selection, always choosing the first element as pivot, and an already sorted array.</p> <pre><code>[0,1,2,3,4] </code></pre> <p>partition, pivot goes in position 0, the smaller subarray is empty. The recursive call for the larger subarray <code>[1,2,3,4]</code>, allocates a new stack frame (so there are now two stack frames). Same principle, the next recursive call with the subarray <code>[2,3,4]</code> allocates a third stack frame, etc.</p> <p>If one has end-recursion removal, i.e. the stack frame is reused, one has the same guarantees as with the manual stack above.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload