Re: qsort and arbitrary types

From: James Giles (jamesgiles_at_worldnet.att.net)
Date: 06/11/04

  • Next message: ArmINVALID_at_bbcc.uk: "Re: clearwin+" 
    Date: Fri, 11 Jun 2004 00:47:27 GMT

    David Frank wrote:
    > quicksort algorithm is short enuf to duplicate it into a generic
    > solution.. ie:

    That's what I said yesterday. Of course, I'd have written
    a standard conforming code for the sort. And, I'd have written
    an efficient version that was not recursive and made no redundant
    compares during the partitioning. And, as I said, the code that
    all versions shared would be in an include file, rather than
    writing it separately several times. Also, why you used a module
    to contain the generic interface, but not the code is incomprehensible:
    it just makes the interface block more verbose and harder to read.
    And, the procedure needs only one argument rather than three:
    the array itself (you can pass a slice which will contain its own
    bounds, assuming you insist on leaving the code recursive).
    And, why you maintained you indices as if the arrays were
    zero-based and then always had to add one back to make them
    legitimate indices again is also incomprehensible. And, the stack
    requirement of your version is potentially one less than the size
    of the argument array - an amount that may terminate the program
    if the array to be sorted already requires a lot of memory. Quicksort
    can be written to use a stack of, at most, the log (base 2) of the
    size of the array. And, qsort is not particularly efficient for small
    partitions. Other optimizations are also applicable.

    I guess I was wrong when I said that we all knew quicksort
    well enough that I didn't have to go into its details. 

    -- 
J. Giles
  • Next message: ArmINVALID_at_bbcc.uk: "Re: clearwin+"

    Relevant Pages

    • Re: Fastest Date Sort
      ... With the QuickSort currently working in my app, I have to assume I'm not ... giving it anything that would cause this 'stack' overflow concern. ... >> Array of UDTs when the sort is completed. ...
      (comp.lang.basic.visual.misc)
    • 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: Fastcode poll - Should Sort include worst case situations
      ... median algorithm, not O), there exists sequences that will beat ... quicksort and make it O. ... by many compiler vendors is "Engineering a Sort ... If it detects that a portion of an array is responding badly, ...
      (borland.public.delphi.language.basm)
    • [PATCH] lib/qsort
      ... This patch introduces an implementation of qsort to lib/. ... I've benchmarked many variants of quicksort implementations on array sizes ... +void qsort_swap ...
      (Linux-Kernel)
    • Re: qsort and arbitrary types
      ... >> quicksort algorithm is short enuf to duplicate it into a generic ... > to contain the generic interface, but not the code is incomprehensible: ... > the array itself (you can pass a slice which will contain its own ... > legitimate indices again is also incomprehensible. ...
      (comp.lang.fortran)