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

    {
    >I'm in need of a FAST way of finding the largest and the smallest
    >30 numbers out of about 1000 different numbers.
    > ...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.
    >  ...Here's a QuickSort demo Program that should help you With the
    >  sort: ...

     Stop the presses, stop the presses!

     Remember the recent Integer sort contest, on the Intelec Programming
     conference?  The fastest method was a "counting" sort technique, which
     used the Integers (to be sorted) as indexes of an Array.

     You asked John Kuhn how it worked, as his example code was in messy
     C.  I sent you an explanation, along With example TP source.  Around
     that time my link to Intelec was intermittently broken; I didn't
     hear back from you - so you may not have received my message (dated
     Jan.02.1993).  I hope you won't mind if I re-post it here and now...

     In a message With John Kuhn...
    > Simply toggle the sign bit of the values beFore sorting. Everything
    > falls into place appropriately from there.
    >  ...OK, but how about toggling them back to their original
    >  state AFTER sorting? (I want to maintain negative numbers)
    >  How can you tell which data elements are negative numbers???

     Hi Guy,

     if you've got all of this under your belt, then please disregard
     the following explanation ...

     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.  The Array size represents the number
     of all possible (16-bit) Integers... -32768 to 32767.

     The "Count Sort" involves taking an Integer, toggling its high bit
     (whether the Integer is originally positive or negative), then
     using this tweaked value as an index into the Array.  The tweaked
     value is used only as an Array index (it becomes an unsigned
     index somewhere within 0..FFFFh, inclusive).

     The Array elements, which are initialized to zero, are simply the
     counts of the _occurrences_ of each Integer.  The original Integers,
     With proper sign, are _derived_ from the indexes which point to
     non-zero elements (after the "sort")... ie. an original Integer is
     derived by toggling the high bit of a non-zero element's index.

     Array elements of zero indicate that no Integer of the corresponding
     (derived) value was encountered, and can be ignored.  if any element
     is non-zero, its index is used to derive the original Integer.  if
     an Array element is greater than one (1), then the corresponding
     Integer occurred more than once.

     A picture is worth 1000 Words:  The following simplified example
     sorts some negative Integers.  The entire Count Sort is done by
     a Single For-do-inC() loop - hence its speed.  The xors do the
     required high-bit toggling ...
    }

    Program DemoCountSort; { Turbo Pascal Count Sort.  G.Vigneault }

    { some negative Integers to sort ... }
    Const
      SomeNegs        : Array [0..20] of Integer =
                           (-2,-18,-18,-20000,-100,-10,-8,-11,-5,
                            -1300,-17,-1,-16000,-4,-12,-15,-19,-1,
                            -31234,-6,-7000 );

    { pick an Array to acComplish Count Sort ... }
    Var
      NegNumArray     : Array [$0000..$7FFF] of Byte;
    { PosNumArray     : Array [$8000..$FFFF] of Byte;            }
    { AllNumArray     : Array [$0000..$FFFF] of Byte;  use heap  }
      Index           : Word;
      IntCount        : Byte;

    begin
      { Initialize }
      FillChar( NegNumArray, Sizeof(NegNumArray), 0 );

      { Count Sort (the inC does this) ... }

      For Index := 0 to 20 do
        { Just 21 negative Integers to sort }
        inC( NegNumArray[ Word(SomeNegs[Index] xor $8000) ]);

      { then display the sorted Integers ... }
      For Index := 0 to $7FFF do
        { Check each Array element }
        For IntCount:= 1 to NegNumArray[Index] do
          { For multiples }
          WriteLn( Integer(Index xor $8000) ); { derive value }

    end { DemoCountSort }.

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