Re: Help needed for a sorting code in the literature

From: Gregory G Rose (ggr_at_qualcomm.com)
Date: 12/30/04

  • Next message: Andrew Swallow: "Re: [Lit.] Buffer overruns" 
    Date: 30 Dec 2004 12:12:33 -0800

    In article <cr1e53$n8s$03$1@news.t-online.com>,
    Mok-Kong Shen <mok-kong.shen@t-online.de> wrote:
    >
    >The code of the heapsort algorithm as given in books by
    >e.g. Sedgewick deals with arrays with indices of the kind
    >a[1..n]. For PLs like C, one would like to sort arrays with
    >indices of the kind a[0..n-1]. I have found sofar only one
    >book that gives code for the latter case, namely "Numerical
    >Recipes in C++" by W. H. Press et al. (which itself refers
    >to Sedgewick). I adapted the code there (which is in C++
    >and is capable of dealing with a variety of data types being
    >sorted) to C for sorting arrays of 'int'. However, the
    >resulting code does not always function correctly. As concrete
    >examples, of 6 random sample cases tested for an 'int' array
    >of size 5 consisting of [0..4] the following input
    >
    > 2 1 3 0 4
    >
    >was wrongly sorted to
    >
    > 0 1 2 4 3
    >
    >while the following inputs
    >
    > 3 0 4 2 1
    > 4 1 0 2 3
    > 3 0 1 4 2
    > 2 3 1 4 0
    >
    >were all processed correctly.
    >
    >Since I only have the book but not the corresponding (original)
    >software, I couldn't be sure whether this is due to my coding
    >error in adapting the code from the text of the book or whether
    >this is due to an error of the authors of the book (though I
    >have carefully checked my coding several times to be sure that
    >it corresponds to the code given in the book). If there is
    >some person of our group who happens to possess the original
    >software of the book, I should appreciate very much to know
    >a confirmation/refutation of my computing result above.
    >
    >M. K. Shen
    >

    I can't help you with the book, but I might be
    able to help you with a possible problem in
    their/your translation.

    Heapsort works by forming a "heap", which has a
    certain invariant: that all elements twice as far
    down the array as the current element are
    {greater, or less, than} (depending on just how
    you implement) it.

    Now, when your array origin is 1, "twice as far
    down" is expressed as:
      {a[i] > a[2*i] && a[i] > a[2*i + 1]).
    But if your array is origin 0, it *should*
    be expressed as:
      (a[i] > a[2*i + 1] && a[i] > a[2*i + 2]).
    (All this ignoring that you need to
    check whether you've run off the end of the
    array, of course. :-) Somewhat surprisingly,
    getting this wrong will still form something very
    much like a heap, and hence the heapsort
    algorithm will *almost* sort your input, and
    often will get it right by luck. (I know -- I've
    been there.)

    I think that's what's happening to you.

    I like heapsort -- it suffers no worst-case
    behaviours like quicksort; it always runs in n
    log n time.

    Greg. 

    -- 
Greg Rose
232B EC8F 44C6 C853 D68F  E107 E6BF CD2F 1081 A37C
Qualcomm Australia: http://www.qualcomm.com.au
  • Next message: Andrew Swallow: "Re: [Lit.] Buffer overruns"

    Relevant Pages

    • Re: Easy balanced tree
      ... We put the items or pointers to the items into an array. ... I don't have the original post any more, so I respond here to the ... You have reinvented the heap data structure, such as used in heapsort. ...
      (comp.lang.forth)
    • Re: Quicksort pathological behavior?
      ... > arrays) or mergesort. ... First, heapsort works fine for binary trees too, in fact ... secondary key to make heapsort be stable, or copying the whole array to ... time-enqueued is the best way to achieve stable-sort behaviour.) ...
      (comp.programming)
    • Re: can a character be negative?
      ... Is the code for the 1-based heap simpler? ... And if an algorithm is being adapted from elsewhere, it's best to stick to it's original array base, if you want it to still work. ... you apply the Heapsort algorithm to it if you insist on the 1-based ... VLA) an array one slot larger, copy the original data into the new ...
      (comp.lang.c)
    • Re: Help needed for a sorting code in the literature
      ... So is qsort(), which indeed might be implemented as ... I had the impression (I am not ... more than one "shape" for an array, ...
      (sci.crypt)
    • Re: THATS IT !!
      ... >lot of work to find out that an array element is ... Greg Rose ...
      (sci.crypt)