[Back to SORTING SWAG index] [Back to Main SWAG index] [Original]

    {>...Assuming that the 1000 numbers are in random-order, I imagine
    > that the simplest (perhaps fastest too) method would be to:
    >    1- Read the numbers in an Array.
    >    2- QuickSort the Array.
    >    3- First 30 and last 30 of Array are the numbers you want.

    >Stop the presses, stop the presses!

      <grin>

    >Remember the recent Integer sort contest, on the Intelec
    >Programming conference?

      ...Ah, yes... I always tend to Forget about that method.
      Yes, a "count" sort would definitely be the fastest method
      of sorting random numerical data.
      ...What I had a few troubles figuring out from that post
      in the Intelec confrence, wasn't the "count sort" method,
      but rather the "radix sort" or "digital sort" method,
      where specific bits within each data element are used
      to sort the data.

      ...Here's the algorithm listed in Robert Sedgewick's
      "Algorithms" book, published by Addison-Wesley Publishing
      Company, ISBN 0-201-06673-4 :
    }

    Procedure RadixExchange(l, r, b:Integer);
    Var
      t, i, j : Integer;
    begin
      if (r > l) and (b >= 0) then
      begin
        i := l;
        j := r;
        Repeat
          While (bits(a[i], b, 1) = 0) and (i < j) do
            i := I + 1;
          While (bits(a[j], b, 1) = 1) and (i < j) do
            j := j - j;
          t := a[i];
          a[i] := a;
          a[j] := t;
        Until (j = i);
        if bits(a[r], b, 1) = 0 then
          j := j + 1;
        RadixExchange(l, (j - 1), b - 1);
        RadixExchange(j, r, (b - 1));
      end;
    end;

    {
    >By toggling the high bit, the Integers are changed in a way that,
    >conveniently, allows sorting by magnitude: from the "most negative"
    >to "most positive," left to right, using an Array With unsigned
    >indexes numbering 0...FFFFh.

      ...Why bother With the bit toggling at all? Why not just define
      the Array's range as being:  Array[-32768..32767] of Byte;
    }

[Back to SORTING SWAG index] [Back to Main SWAG index] [Original]