home *** CD-ROM | disk | FTP | other *** search
/ POINT Software Programming / PPROG1.ISO / pascal / swag / sorting.swg / 0021_RADIX2.PAS.pas < prev    next >
Encoding:
Pascal/Delphi Source File  |  1993-05-28  |  1.8 KB  |  62 lines
  1. {>...Assuming that the 1000 numbers are in random-order, I imagine
  2. > that the simplest (perhaps fastest too) method would be to:
  3. >    1- Read the numbers in an Array.
  4. >    2- QuickSort the Array.
  5. >    3- First 30 and last 30 of Array are the numbers you want.
  6.  
  7. >Stop the presses, stop the presses!
  8.  
  9.   <grin>
  10.  
  11. >Remember the recent Integer sort contest, on the Intelec
  12. >Programming conference?
  13.  
  14.   ...Ah, yes... I always tend to Forget about that method.
  15.   Yes, a "count" sort would definitely be the fastest method
  16.   of sorting random numerical data.
  17.   ...What I had a few troubles figuring out from that post
  18.   in the Intelec confrence, wasn't the "count sort" method,
  19.   but rather the "radix sort" or "digital sort" method,
  20.   where specific bits within each data element are used
  21.   to sort the data.
  22.  
  23.   ...Here's the algorithm listed in Robert Sedgewick's
  24.   "Algorithms" book, published by Addison-Wesley Publishing
  25.   Company, ISBN 0-201-06673-4 :
  26. }
  27.  
  28. Procedure RadixExchange(l, r, b:Integer);
  29. Var
  30.   t, i, j : Integer;
  31. begin
  32.   if (r > l) and (b >= 0) then
  33.   begin
  34.     i := l;
  35.     j := r;
  36.     Repeat
  37.       While (bits(a[i], b, 1) = 0) and (i < j) do
  38.         i := I + 1;
  39.       While (bits(a[j], b, 1) = 1) and (i < j) do
  40.         j := j - j;
  41.       t := a[i];
  42.       a[i] := a;
  43.       a[j] := t;
  44.     Until (j = i);
  45.     if bits(a[r], b, 1) = 0 then
  46.       j := j + 1;
  47.     RadixExchange(l, (j - 1), b - 1);
  48.     RadixExchange(j, r, (b - 1));
  49.   end;
  50. end;
  51.  
  52. {
  53. >By toggling the high bit, the Integers are changed in a way that,
  54. >conveniently, allows sorting by magnitude: from the "most negative"
  55. >to "most positive," left to right, using an Array With unsigned
  56. >indexes numbering 0...FFFFh.
  57.  
  58.   ...Why bother With the bit toggling at all? Why not just define
  59.   the Array's range as being:  Array[-32768..32767] of Byte;
  60. }
  61.  
  62.