Re: Quicksort

"robertwessel2@xxxxxxxxx" wrote:
"robertwess...@xxxxxxxxx" <robertwess...@xxxxxxxxx> wrote:
Adak <adak_d...@xxxxxxxxxxxxx> wrote:

Not imo. I've tested an iterative version of Quicksort, and it
was just slightly faster. IMO it wasn't worth the bother of
ensuring that the stack space was adequate. Also, the recursive
version is a beauty. The iterative version is certainly not.

Do you mean the fully recursive version of Quicksort, where both
partitions are sorted recursively, or the semi-recursive version
where only the smaller partition is sorted recursively, and the
larger one iteratively?

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).

--
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

  • Re: Quicksort
    ... version, unless, of course you can afford order N stack space. ... trivially easy to do it yourself, ... partition, you will use no more than logstack space. ... If the compiler does tail recursion elimination, ...
    (comp.programming)
  • Re: The benefits of recursive programming
    ... programming instead of looping, even in lower-level languages like C, is beneficial for writing maintainable, verifiable code. ... Your example of using recursion to compute ... The recursive version of the report-printing procedure actually runs in constant stack space when compiled on GCC 3.4. ...
    (comp.programming)
  • Re: Increase .NET stack space?
    ... Dacon Software Consulting ... > Is there any way to increase the .NET stack space? ... I am going to suggest that he rewrite his recursion ... > there were any way to increase the .NET stack size... ...
    (microsoft.public.dotnet.framework)
  • Re: Quicksort
    ... version, unless, of course you can afford order N stack space. ... That won't normally control the recursion depth, ...
    (comp.programming)
  • out of stack space error (no recursion used)
    ... There is a javscript code that causes "out of stack space" error. ... does not include any recursion but does include iterations. ... In the second portion of code the string from the array (which is actually ... I am using recursion as well in some OTHER CODE and that recursion works ...
    (microsoft.public.scripting.jscript)