Re: Minlist, Maxlist (sorting an array)

[Alex Matulich <alex@xxxxxxxxxxxxxx>]

DH wrote:
>Bob Fulks provided the following code some time ago for sorting any size

In spite of the comment saying it's a "very fast" sort routine,
it's not.  It's a somewhat more efficient variation of a bubble
sort.  This is still an O(N^2) sort (meaning the execution time is
proportional to N^2, the square of the length of the array).

Here's an implementation of heapsort, which I described a
long time ago on this list, before I really learned EasyLanguage:
http://www.purebytes.com/archives/omega/2002/msg05534.html

That version won't work (because it uses the variables I and L,
which are reserved in EL).  Below is a corrected version.  This is
an O(N log N) sort, significantly faster for large arrays.

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

{Function: _heapsort_a
 by Alex Matulich
 Adapted from _Numerical Recipes in C_

 This function sorts an array ra[] from index 0 to N.
 }

inputs: ra[m](NumericArrayRef), N(NumericSimple);

vars: NN(0), ii(0), ir(0), jj(0), ll(0), rra(0), lp1(true), lp2(true);
if m < N then NN = m else NN = N;
if NN > 1 then begin
    ll = IntPortion(0.5*NN)+1;
    ir = NN;
    while lp1 begin
        if ll > 1 then begin
            ll = ll-1;
            rra = ra[ll];
        end else begin
            rra = ra[ir];
            ra[ir] = ra[0];
            ir = ir-1;
            if ir = 0 then begin
                ra[0] = rra;
                lp1 = false;
            end;
        end;
        ii = ll;
        jj = ll+ll;
        lp2 = true;
        while lp1 and lp2 and jj <= ir begin
            if jj < ir and ra[jj] < ra[jj+1] then jj = jj+1;
            if rra < ra[jj] then begin
                ra[ii] = ra[jj];
                ii = jj;
                jj = jj+jj;
            end else lp2 = false;
        end;
        ra[ii] = rra;
    end;
end;
_heapsort_a = NN; {dummy return value}

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

-Alex