[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]