Re: Help needed for a sorting code in the literature

From: Mok-Kong Shen (mok-kong.shen_at_t-online.de)
Date: 12/31/04 

Date: Fri, 31 Dec 2004 12:37:32 +0100

Gregory G Rose wrote:
>
> Mok-Kong Shen <mok-kong.shen@t-online.de> wrote:
............................
[snip]

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

Thank you for your comments. Since you have good knowledge
and experience with the algorithm, may I ask your favour
to cast a glance at my adaptation (in the attachment),
which in my conviction is a very careful adaptation to
C (for the special case of 'int' array) from the code text
of the book that is also available (thanks to Bob Harris
for the link) at the following URL?

   http://www.library.cornell.edu/nr/bookcpdf/c8-3.pdf

Many thanks in advance.

M. K. Shen
---------------------------------------

// adapted from Numerical Recipes in C++, p.340-341.
// possibly wrong due to error in the book.

void siftdown(int a[], int l, int r)
{ int j,jold,v;
   v=a[l];
   jold=l;
   j=l+1;
   while (j<=r)
   { if (j<r && a[j]<a[j+1]) j++;
     if (v>=a[j]) break;
        a[jold]=a[j];
        jold=j;
        j=2*j+1;
   }
   a[jold]=v;
}

void hpsort(int a[], int n)
{ int i,t;
   for (i=n/2-1; i>=0; i--) siftdown(a,i,n-1);
   for (i=n-1; i>0; i--)
   { t=a[0]; a[0]=a[i]; a[i]=t;
     siftdown(a,0,i-1);
   }
}

Relevant Pages