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 15:08:22 +0100

BRG wrote:

> Mok-Kong Shen wrote:
..........
[snip]

> Here is a C++ version of a bottom up heapsort that should be easy to
> convert to C. No guarantees that it is correct though - posting code
> here is a virtual guaranetee that someone will find bugs in it :-)
>
> template<class T> static void heap_sub(T x[], int i, const int n)
> { int j;
> while((j = i + i) <= n)
> {
> if(j < n && x[j] <= x[j + 1])
> ++j;
> if(x[i] >= x[j])
> return;
> T y(x[i]); x[i] = x[j]; x[j] = y;
> i = j;
> }
> }
>
> template<class T> void heapsort(T x[], const int n)
> {
> for(int i = (n >> 1); i > 0; --i)
> heap_sub(x, i - 1, n);
>
> for(int i = n - 1; i > 0; --i)
> {
> T y(x[0]); x[0] = x[i]; x[i] = y;
> heap_sub(x, 0, i - 1);
> }
> }

Could you kindly check whether my coversion of your code in
the attachment was properly done? It didn't correctly function
in my test run on the data:

    3 0 4 2 1

Thanks.

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

void heap_sub(int x[], int i, int n)
{ int j,y;
   while((j = i + i) <= n)
   { if(j < n && x[j] <= x[j + 1]) ++j;
     if(x[i] >= x[j]) return;
     y = x[i]; x[i] = x[j]; x[j] = y;
     i = j;
   }
}

void heapsort(int x[], int n)
{ int i,y;
   for (i = (n >> 1); i > 0; --i)
     heap_sub(x, i - 1, n);
   for (i = n - 1; i > 0; --i)
     { y = x[0]; x[0] = x[i]; x[i] = y;
       heap_sub(x, 0, i - 1);
     }
}

Relevant Pages