home *** CD-ROM | disk | FTP | other *** search
/ POINT Software Programming / PPROG1.ISO / pascal / swag / sorting.swg / 0008_COUNT2.PAS.pas < prev    next >
Encoding:
Pascal/Delphi Source File  |  1993-05-28  |  4.1 KB  |  102 lines
  1. {
  2. >I'm in need of a FAST way of finding the largest and the smallest
  3. >30 numbers out of about 1000 different numbers.
  4. > ...Assuming that the 1000 numbers are in random-order, I imagine
  5. > that the simplest (perhaps fastest too) method would be to:
  6. >    1- Read the numbers in an Array.
  7. >    2- QuickSort the Array.
  8. >    3- First 30 and last 30 of Array are the numbers you want.
  9. >  ...Here's a QuickSort demo Program that should help you With the
  10. >  sort: ...
  11.  
  12.  Stop the presses, stop the presses!
  13.  
  14.  Remember the recent Integer sort contest, on the Intelec Programming
  15.  conference?  The fastest method was a "counting" sort technique, which
  16.  used the Integers (to be sorted) as indexes of an Array.
  17.  
  18.  You asked John Kuhn how it worked, as his example code was in messy
  19.  C.  I sent you an explanation, along With example TP source.  Around
  20.  that time my link to Intelec was intermittently broken; I didn't
  21.  hear back from you - so you may not have received my message (dated
  22.  Jan.02.1993).  I hope you won't mind if I re-post it here and now...
  23.  
  24.  In a message With John Kuhn...
  25. > Simply toggle the sign bit of the values beFore sorting. Everything
  26. > falls into place appropriately from there.
  27. >  ...OK, but how about toggling them back to their original
  28. >  state AFTER sorting? (I want to maintain negative numbers)
  29. >  How can you tell which data elements are negative numbers???
  30.  
  31.  Hi Guy,
  32.  
  33.  if you've got all of this under your belt, then please disregard
  34.  the following explanation ...
  35.  
  36.  By toggling the high bit, the Integers are changed in a way that,
  37.  conveniently, allows sorting by magnitude: from the "most negative"
  38.  to "most positive," left to right, using an Array With unsigned
  39.  indexes numbering 0...FFFFh.  The Array size represents the number
  40.  of all possible (16-bit) Integers... -32768 to 32767.
  41.  
  42.  The "Count Sort" involves taking an Integer, toggling its high bit
  43.  (whether the Integer is originally positive or negative), then
  44.  using this tweaked value as an index into the Array.  The tweaked
  45.  value is used only as an Array index (it becomes an unsigned
  46.  index somewhere within 0..FFFFh, inclusive).
  47.  
  48.  The Array elements, which are initialized to zero, are simply the
  49.  counts of the _occurrences_ of each Integer.  The original Integers,
  50.  With proper sign, are _derived_ from the indexes which point to
  51.  non-zero elements (after the "sort")... ie. an original Integer is
  52.  derived by toggling the high bit of a non-zero element's index.
  53.  
  54.  Array elements of zero indicate that no Integer of the corresponding
  55.  (derived) value was encountered, and can be ignored.  if any element
  56.  is non-zero, its index is used to derive the original Integer.  if
  57.  an Array element is greater than one (1), then the corresponding
  58.  Integer occurred more than once.
  59.  
  60.  A picture is worth 1000 Words:  The following simplified example
  61.  sorts some negative Integers.  The entire Count Sort is done by
  62.  a Single For-do-inC() loop - hence its speed.  The xors do the
  63.  required high-bit toggling ...
  64. }
  65.  
  66.  
  67. Program DemoCountSort; { Turbo Pascal Count Sort.  G.Vigneault }
  68.  
  69. { some negative Integers to sort ... }
  70. Const
  71.   SomeNegs        : Array [0..20] of Integer =
  72.                        (-2,-18,-18,-20000,-100,-10,-8,-11,-5,
  73.                         -1300,-17,-1,-16000,-4,-12,-15,-19,-1,
  74.                         -31234,-6,-7000 );
  75.  
  76. { pick an Array to acComplish Count Sort ... }
  77. Var
  78.   NegNumArray     : Array [$0000..$7FFF] of Byte;
  79. { PosNumArray     : Array [$8000..$FFFF] of Byte;            }
  80. { AllNumArray     : Array [$0000..$FFFF] of Byte;  use heap  }
  81.   Index           : Word;
  82.   IntCount        : Byte;
  83.  
  84. begin
  85.   { Initialize }
  86.   FillChar( NegNumArray, Sizeof(NegNumArray), 0 );
  87.  
  88.   { Count Sort (the inC does this) ... }
  89.  
  90.   For Index := 0 to 20 do
  91.     { Just 21 negative Integers to sort }
  92.     inC( NegNumArray[ Word(SomeNegs[Index] xor $8000) ]);
  93.  
  94.   { then display the sorted Integers ... }
  95.   For Index := 0 to $7FFF do
  96.     { Check each Array element }
  97.     For IntCount:= 1 to NegNumArray[Index] do
  98.       { For multiples }
  99.       WriteLn( Integer(Index xor $8000) ); { derive value }
  100.  
  101. end { DemoCountSort }.
  102.