Re: Quicksort

On Jan 8, 12:52 am, CBFalconer <cbfalco...@xxxxxxxxx> wrote:
Stack size is unavoidably a problem with the fully recursive
version, unless, of course you can afford order N stack space.

Or your compiler guarantees to do tail-recursion elimination.

That won't normally control the recursion depth, since each level
has to depend on the relative size of the segments.  It is
trivially easy to do it yourself, and ensure the depth never
exceeds ln2(size).


If you recurse in the correct order (smaller partition first), and the
compiler does tail recursion elimination for the second (larger)
partition, you will use no more than log(n) stack space. Basically
what's happening is that the compiler converts the fully recursive
form to the semi recursive form of quicksort by looping on the second
(larger) partition.
.

Relevant Pages

  • egroupware, anyone?
    ... Fortunately the recursion depth is bounded so this below is just the ... There is no single government agency that views sustainability through a broad ...
    (Fedora)
  • Re: Quicksort
    ... version, unless, of course you can afford order N stack space. ... That won't normally control the recursion depth, ...
    (comp.programming)
  • Re: Troubles with memory allocation
    ... > # exponential growth in recursion depth. ... > a protocol stack or a replica of that built in the heap: ...
    (comp.programming)
  • Re: Quicksort
    ... partitions are sorted recursively, or the semi-recursive version ... version, unless, of course you can afford order N stack space. ... That won't normally control the recursion depth, ...
    (comp.programming)
  • Re: [patch] Re: Problem with exiting threads under NPTL
    ... > I realize that the recursion should be just one deep (the leader of the ... > looks trivial to avoid it, and any automated source checking tool would be ... explicitly stating the recursion depth right where it happens makes ... send the line "unsubscribe linux-kernel" in ...
    (Linux-Kernel)