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:41:56 +0100

Mok-Kong Shen wrote:
>
>
> 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