home *** CD-ROM | disk | FTP | other *** search
/ PC-X 1997 October / pcx14_9710.iso / swag / sorting.swg / 0056_UltraSort.pas < prev    next >
Encoding:
Pascal/Delphi Source File  |  1995-05-26  |  3.9 KB  |  93 lines
  1. {
  2. Here's a new sorting routine I developed... If someone know that someone
  3. already did this, leave a message to me... Ok.. On with the sorting
  4. routine...
  5.  
  6. (********************************CutHERE******************************)
  7. {
  8.                      UltraSORT   Jere Sanisalo
  9.                    \***************************/
  10.  
  11.    This is a new (I think) method of sorting... It uses a table, which
  12.    size can be different every time you use it... Now I am going to tell
  13.    you how this example works (not only the general method). This example
  14.    makes 32000 numbers (words) and randomizes them. Then comes the "WOW"
  15.    part... It sorts them all 100 times... So it processes 3.2 megabytes.
  16.    It took about 8 seconds in my 66 Mzh machine. You all must understand
  17.    all of this code, but I'm still going to explain how the sorting is
  18.    done (for the lazy people). First it (USort procedure) makes a "table"
  19.    that is sized as big as a word can can be ($FFFF), and clears is. Now
  20.    we have a table full of zeros and the numbers to be sorted. Then it
  21.    goes through the number one by one and looks what they are. After that
  22.    it increases the value in the table at the position that the number tells
  23.    by one. Pretty tricky, huh? So if we have a number to process, let's say
  24.    it is 89. Then it increses the value at the table positioned 89 by one.
  25.    (In pascal: Inc(Table[Number]) ) This example just doesn't use straight
  26.    variable. It reserves one memory segment and uses it, but the way the
  27.    sorting is done is not changed. After we have processed the whole number-
  28.    stream we have all information we need in the table. So now we just go
  29.    through the table, and if its value is more that 0 then put the value
  30.    somewhere where you want the final results (In order, of course). When
  31.    that is done, we are finished! We have the sorted table ready!! Enjoy it,
  32.    but if you use it           ====>  GIVE CREDITS TO ME  <====
  33.  
  34.   BTW. There are some restrictions... You can't have more that 256
  35.   pieces of the same number. And the number can't be greater than $FFFF.
  36.   These retrictions are possible to break, but I am lazy... ;( On with
  37.   the code...
  38. }
  39.  
  40. uses dos,crt;
  41.  
  42. const
  43.    numtosort = 32000;                           {How many numbers to sort}
  44.  
  45. var
  46.    numbers : array [1..numtosort] of word;      {Numbers to be sorted}
  47.    i,j,b,a : word;                              {Just some variables}
  48.  
  49. procedure usort;
  50. var
  51.    p : pointer;
  52.    segm,maxnum,minnum : word;
  53.  begin
  54.  getmem(p,$ffff); segm:=seg(p^);                {Make the table to be used}
  55.  fillchar(p^,$ffff,0);                          {in the sorting}
  56. {This version looks also for the maximum and minimum numbers for speed...}
  57.  maxnum:=0; minnum:=$ffff;
  58.  for i:=1 to numtosort do                       {This "plots the numbers to}
  59.      begin                                      {the table...}
  60.      if maxnum<numbers[i] then maxnum:=numbers[i];
  61.      if minnum>numbers[i] then minnum:=numbers[i];
  62.      inc(mem[segm:numbers[i]]);
  63.      end;
  64.  b:=1;
  65.  for i:=minnum to maxnum do                     {This gets the procecced}
  66.      begin                                      {numbers back to Numbers[]-}
  67.      if mem[segm:i]>0 then                      {variable}
  68.         begin
  69.         for j:=0 to mem[segm:i]-1 do
  70.             numbers[b+j]:=i;
  71.         inc(b,mem[segm:i]);
  72.         end;
  73.      end;
  74.  freemem(p,$ffff);                              {Free the table's memory}
  75.  end;
  76.  
  77. begin
  78. randomize;                                      {Randomize the numbers}
  79. for i:=1 to numtosort do
  80.     numbers[i]:=random($ffff);
  81. for a:=1 to 100 do                              {Sort 100 times}
  82.     begin
  83.     write('.');
  84.     usort;
  85.     end;
  86. writeln;
  87. for i:=1 to numtosort do                        {Write the finished results}
  88.     begin
  89.     writeln(numbers[i]);
  90.     if keypressed then begin readkey; readkey; end;
  91.     end;
  92. end.
  93.