Databases
StackOverflow2013
Postsdbo
POquick sort implementation using stack
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POquick sort implementation using stack
    text
    copied!<p>I am reading a quick sort implementation using a stack at the following link.</p> <p><a href="http://codeidol.com/community/java/stack-size/11581/#part-3" rel="nofollow">link</a></p> <p>My question is regarding the following paragraph.</p> <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, so that the stack needs to contain room for only about lg N entries. This maximum stack usage occurs when the partition always falls at the center of the file. For random files, the actual maximum stack size is much lower; for degenerate files it is likely to be small.</p> <p>This technique does not necessarily work in a truly recursive implementation, because it depends on end- or tail-recursion removal. If the last action of a procedure is to call another procedure, some programming environments will arrange things such that local variables are cleared from the stack before, rather than after, the call. Without end-recursion removal, we cannot guarantee that the stack size will be small for quicksort.</p> </blockquote> <ol> <li><p>What does the author mean by "that each entry on the stack is no more than one-half of the size of the one below it"? Could you please give an example of this.</p></li> <li><p>How did the author came to the conclusion that the stack needs space for only about <code>lg N</code> entries?</p></li> <li><p>What does authore mean by "Without end-recursion removal, we cannot guarantee that the stack size will be small for quicksort" ?</p></li> </ol> <p>Thanks for your time and help.</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