Quicksort

Quicksort is a typical recursive procedure.
It can, of course, also be implemented iteratively
by remembering the indices (left, right) with a stack.

So, there should be no significant gain in storage space
(compared to the systems local stack) but in speed because there
are no function calls.


Is this thinking justified?
.

Relevant Pages

  • Re: Quicksort
    ... worth the bother of ensuring that the stack space was adequate. ... is to set a reasonable maximum on the recursion ... case, I usually use either selection sort or a bubble sort variant, such as ... suited to the problem areas of quicksort). ...
    (comp.programming)
  • Re: non-recursive quicksort for 2-D arrays?
    ... You are saying don't use a quicksort as it causes stack problems, but use a Shell Sort, which doesn't ... bigger parts of the array, ... Dim lArrayChunk As Long ...
    (microsoft.public.vb.general.discussion)
  • Re: Fastest Date Sort
    ... > giving it anything that would cause this 'stack' overflow concern. ... because this Quicksort is really kicking some timing butt! ... I've been using a version of Randy's quick sort in a production app with 20 ...
    (comp.lang.basic.visual.misc)
  • Re: When is a stack used in real life?
    ... >> compiler created stack overflow as is often seen in QuickSort ... >The recursion is not the speed limit for Quicksort, ...
    (comp.programming)
  • Re: Fastcode poll - Should Sort include worst case situations
    ... He has also proven that QuickSort is the most optimal comprison-based sort ... distribution where everything is linear. ... the larger partition is placed on the stack. ...
    (borland.public.delphi.language.basm)