Re: Quicksort

On Jan 8, 4:58 pm, CBFalconer <cbfalco...@xxxxxxxxx> wrote:
"robertwess...@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.


OK:

quicksort(partition p)
{
leftpart,rightpart=partition(p)
smallpart,largepart=orderbysize(leftpart,rightpart)
quicksort(smallpart)
quicksort(largepart)
}

What problem? If the compiler does tail recursion elimination, the
second recursive call is turned into a loop, and the only growth in
stack size happens when the smaller partition is recursively sorted,
which trivially ensures a limit of log(n) stack usage.

IOW, tail recursion elimination allows the compiler to convert the
above into the explicitly semi-recursive version of quicksort:

quicksort(partition p)
{
loop while ((size of p) > 1)
{
leftpart,rightpart=partition(p)
smallpart,largepart=orderbysize(leftpart,rightpart)
quicksort(smallpart)
p=largepart
}
}

If the compiler does *not* do tail recursion elimination, stack usage
is proportional to n in the worst case. Given that most compiler
don't actually do tail recursion elimination, and many of the ones
that do don't provide strong guarantees as to when it happens, a fully
recursive quicksort implementation (as first pseudocode sample) should
almost always be considered flawed.
.

Relevant Pages

  • Re: Do buffers always start with the lowest memory address being the first element?
    ... > The C standard does not assume a downward-growing stack, ... > an upward-growing stack. ... C allows but does not require that the array produced ... > machine depends on both the C compiler and the machine. ...
    (comp.lang.c)
  • Re: switch statement, was compiler, status...
    ... Primary Register, Secondary Register, ... Stack, and abit of storage does it. ... This version of Small-C is copyrighted as a revision to Ron Cain's ... Croatia) is "Calculator Compiler" by Senko Rasik. ...
    (alt.lang.asm)
  • Re: subroutine stack and C machine model
    ... On a typical system the stack on entry to the function looks like this ... balance to specify the order of evaluation). ... compiler developer to find out when code can be moved around. ... I think the Standards people used compiler optimization as an excuse ...
    (comp.lang.c)
  • Re: back online again...
    ... really "acceptable") convention. ... stack machine, but the design ... target with my compiler (may need a different name for this though, ... most of this code is not likely to ever go to object files anyways... ...
    (alt.lang.asm)
  • Re: 2.6.25-git2: BUG: unable to handle kernel paging request at ffffffffffffffff
    ... since the compiler is totally free to spill and reload the local variable ... So forget about the prefetch, ... variable onto the stack, since it did that volatime memory access through ... the insane "store and immediately reload from ...
    (Linux-Kernel)