Re: Help needed for a sorting code in the literature

From: BRG (brg_at_nowhere.org)
Date: 12/31/04 

Date: Fri, 31 Dec 2004 13:29:23 +0000

Mok-Kong Shen wrote:

> The code of the heapsort algorithm as given in books by
> e.g. Sedgewick deals with arrays with indices of the kind
> a[1..n]. For PLs like C, one would like to sort arrays with
> indices of the kind a[0..n-1]. I have found sofar only one
> book that gives code for the latter case, namely "Numerical
> Recipes in C++" by W. H. Press et al. (which itself refers
> to Sedgewick). I adapted the code there (which is in C++
> and is capable of dealing with a variety of data types being
> sorted) to C for sorting arrays of 'int'.

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 :-)

    Brian Gladman

-------------------------

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);
        }
}

Relevant Pages

  • Need help for a code in "Numerical Recipes in C++"
    ... e.g. Sedgewick deals with arrays with indices in. ... of 'int' with indices in. ... void siftdown ...
    (sci.math.num-analysis)
  • Help needed for a sorting code in the literature
    ... e.g. Sedgewick deals with arrays with indices of the kind ... sorted) to C for sorting arrays of 'int'. ... I couldn't be sure whether this is due to my coding ...
    (sci.crypt)
  • Re: Help needed for a sorting code in the literature
    ... >> The code of the heapsort algorithm as given in books by ... >> e.g. Sedgewick deals with arrays with indices of the kind ... >> sorted) to C for sorting arrays of 'int'. ...
    (sci.crypt)
  • Re: why cant functions return arrays
    ... int f; ... for such a language restricton. ... have been able to pass and return fixed-size arrays by value by ... Since there were no prototypes in K&R, there was no way to inform the ...
    (comp.lang.c)
  • Re: Implementing an 8 bit fixed point register
    ... It seems like implementing ALU operations on such arrays would ... If one only wants int arithmetic and all-bits logic, ... def bitset ... your approach could be easily modified to support slices: ...
    (comp.lang.python)