[M3devel] subrange value not constant?

[Mika Nystrom]

Martin Bishop writes:
>Hmm, good point about count.  Originally I did initialize to 0, but in 
>the process of trying to get it to work, I must have removed it.
>
>As for min and max, yes the point of the Counting Sort 
>(http://en.wikipedia.org/wiki/Counting_sort) is that min and max are known.
>
>Thanks for the help :)

Well what I mean is this.  Assume you know that counting sort is
appropriate for your data, i.e., that n + k <= n log n for the data
in question (using Wikipedia's notation).

There are two approaches I can think of for implementing the sort.

1. Figure out min and max before calling Sort, by a linear scan, or some
other mechanism.  If this mechanism adds any code at all, it's likely to
add O(n) runtime to the algorithm (because you are making it look at
every element before it goes in).

2. Dispense with min and max and instead generate these dynamically within
the sort.  Initialize them to the first element, and re-allocate the
array when you see any element outside the current range.  This approach
also has O(n) (amortized) cost.

So you'd do, say,

PROCEDURE Sort(VAR a : ARRAY OF INTEGER) =

  PROCEDURE ReLimit(newmin, newmax : INTEGER) =
    BEGIN
      WITH newcount = NEW(REF ARRAY OF CARDINAL, newmax - newmin + 1) DO
        FOR i := FIRST(newcount^) TO min-newmin-1 DO newcount[i] := 0 END;
        FOR i := newmax-max TO LAST(newcount^) DO newcount[i] := 0 END;
        SUBARRAY(newcount^, min-newmin, max-min+1) := count^;
      END;
      count := newcount; min := newmin; max := newmax
    END ReLimit;

  PROCEDURE Tally(v : INTEGER) =
    CONST GrowFactor = 2;
    BEGIN 
      IF    v < min THEN ReLimit(min-(min-v)*GrowFactor, max) 
      ELSIF v > max THEN ReLimit(min, max+(v-max)*GrowFactor)
      END;
      INC(count[v-min])
    END Tally;

  PROCEDURE Initialize() =
    BEGIN
      min := a[0]; max := a[0]; 
      count := NEW(REF ARRAY OF CARDINAL, 1); 
    END Initialize;

  PROCEDURE Reconstruct() =
    VAR ai := FIRST(a);
    BEGIN
      FOR i := FIRST(count^) TO LAST(count^) DO
        WHILE count[i] > 0 DO
          a[ai] := i+min; 
          DEC(count[i]); INC(ai)
        END
      END
    END Reconstruct;

  VAR min, max : INTEGER;
      count : REF ARRAY OF INTEGER;
  BEGIN
    Initialize();

    FOR i := FIRST(a) TO LAST(a) DO
      Tally(a[i])
    END;

    Reconstruct()
  END Sort;

The asymptotic runtime of this version is the same as yours and it
encapsulates all the min, max knowledge, giving a simpler interface,
and it usually means you can remove some min, max code from the
caller.

Modula-3 is really good for this sort of coding.  I find that the
extra effort of simplifying interfaces and making sure the code
works for any input is paid off handsomely and very quickly...

As it says in the Algol-60 report, the code above "has not been run
on a computer".

     Mika