I wonder if anyone in the past reported any bug againt the heapsort in cheapter 8.3 - NR in C. I used the code from online book and experienced problem when I used an array of size 77. The array I used is already sorted ascendingly, the first element has value 192100.0 then it increases by 50 subsequently. I appreciate if anyone could verify it and provide solution. Thanks in advance.

I did a hpsort() on the data you said. It works fine, it seems.

what was the problem?

Roy

The problem was when I tried to sort the array I described, the result indicated that one or few elements were out of order. The elements that are out of order seem to be near to the half way of the array. However, this problem wonn't occur if I tried other array with smaller value and small size array. Very strange!

Why don't you post your code and the results to the forum?
No one is able to help you find answers unless you provide
enough information.

There is a bug in the heap sort routine in the C++ code. For example if we try and sort the following list of numbers

10,9,8,7,6,5,100

then the heap sort routine returns

5,6,7,8,9,100,10

which is obviously wrong. I've amended the example code for the heap sort routine to demonstrate this. This is shown at the end of my post.

The error is in the 'sift_down' function. The 5th line of the code should read
j = 2*l+1
not
j = l+1

Changing this will fix the code.

Hope this helps

Haydyn

Revised Example Code

#include <string>
#include <fstream>
#include <iostream>
#include <iomanip>
#include "nr.h"
#include "print_array.h"
using namespace std;

// Revised Example code to demonstrate
// error in heap sort routine
// by Haydyn Brown - 21st May 2002

int main(void)
{
const int NP=7;
string txt;
int i;
Vec_DP a(NP);

// Test array
a[0] = 10.0;
a[1] = 9.0;
a[2] = 8.0;
a[3] = 7.0;
a[4] = 6.0;
a[5] = 5.0;
a[6] = 100.0;
//ifstream fp("tarray.dat");

//if (fp.fail())
// NR::nrerror("Data file tarray.dat not found");
//getline(fp,txt);
//for (i=0;i<NP;i++) fp >> a[i];
cout << endl << "original array:" << endl;
cout << fixed << setprecision(2);
print_array(a,10,7);
NR::hpsort(a);
cout << endl << "sorted array:" << endl;
print_array(a,10,7);
return 0;
}

There is indeed a bug in the C++ version of hpsort, as reported by Haydn. Line 11 should be

j=2*l+1;

and not

j=l+1;

(For those of you with fonts that make ell look
like one, that's 2*ell + one, and not ell + one)

This bug is only in the C++ version, and not in f77, f90, or C.