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 13:06:59 +0100

Mok-Kong Shen wrote:

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

> 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

Sorry for a accidental duplicted post and for not having
noticed the fact that my adaptation was from the C++ book,
while the above URL is for the C book (of the same authors
and that has apparently combined the two functions in the
C++ book together) that I don't have. I am including below
for comparison with my code the stuff in the C++ book
verbatim (excepting the comments).

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

#include "nr.h"
namespace {
   void sift_down(Vec_IO_DP &ra, const int l, const int r)
   { int j,jold;
     DP a;
     a=ra[l];
     jold=l;
     j=l+1;
     while (j<=r) {
       if (j<r && ra[j]<ra[j+1]) j++;
       if (a>=ra[j]) break;
       ra[jold]=ra[j];
       jold=j;
       j=2*j+1;
     }
     ra[jold]=a;
   }
}

void NR::hpsort(VEC_IO_DP &ra)
{ int i;
   int n=ra.size();
   for (i=n/2-1; i>=0; i--) sift_down(ra,i,n-1);
   for (i=n-1; i>0; i--) {
     SWAP(ra[0],ra[i]);
     sift_down(ra,0,i-1);
   }
}