Re: Quicksort

"robertwessel2@xxxxxxxxx" wrote:
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.

Write out the code and see the problem for yourself.

Please don't delete attributions for material you quote.

--
Chuck F (cbfalconer at maineline dot net)
<http://cbfalconer.home.att.net>
Try the download section.


--
Posted via a free Usenet account from http://www.teranews.com

.

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)