home *** CD-ROM | disk | FTP | other *** search
/ POINT Software Programming / PPROG1.ISO / pascal / swag / sorting.swg / 0023_Radix Sort.pas < prev    next >
Encoding:
Pascal/Delphi Source File  |  1993-05-28  |  2.9 KB  |  134 lines
  1. {
  2. > I agree... unFortunately the Radix algorithm (which is a
  3. > sophisticated modification of a Distribution Sort algorithm) is
  4. > very Complex, highly CPU dependent and highly data dependent.
  5.  
  6. We must be speaking of a different Radix Sort.  Is the sort you are
  7. talking about sort numbers on the basis of their digits?
  8.  
  9. > My understanding is that a Radix sort cannot be implemented in
  10. > Pascal without using a majority of Asm (which means you might as
  11. > well code the whole thing in Asm.)
  12.  
  13. > assembly) or dig up some working code, I would love to play With it!
  14.  
  15. ************************************************************************
  16. *                                                                      *
  17. * Name : Joy Mukherjee                                                 *
  18. * Date : Mar. 26, 1990                                                 *
  19. * Description : This is the Radix sort implemented in Pascal           *
  20. *                                                                      *
  21. ************************************************************************
  22. }
  23.  
  24. Program SortStuff;
  25.  
  26. Uses Crt, Dos;
  27.  
  28. Type
  29.     AType = Array [1..400] of Integer;
  30.     Ptr   = ^Node;
  31.     Node  = Record
  32.           Info : Integer;
  33.           Link : Ptr;
  34.         end;
  35.     LType = Array [0..9] of Ptr;
  36.  
  37. Var
  38.    Ran     : AType;
  39.    MaxData : Integer;
  40.  
  41. Procedure ReadData (Var A : AType; Var MaxData : Integer);
  42.  
  43. Var I : Integer;
  44.  
  45. begin
  46.      MaxData := 400;
  47.      For I := 1 to 400 do A [I] := Random (9999);
  48. end;
  49.  
  50. Procedure WriteArray (A : AType; MaxData : Integer);
  51.  
  52. Var I : Integer;
  53.  
  54. begin
  55.   For I := 1 to MaxData do
  56.     Write (A [I] : 5);
  57.   Writeln;
  58. end;
  59.  
  60. Procedure Insert (Var L : LType; Number, LN : Integer);
  61.  
  62. Var
  63.   P, Q : Ptr;
  64.  
  65. begin
  66.   New (P);
  67.   P^.Info := Number;
  68.   P^.Link := Nil;
  69.   Q := L [LN];
  70.   if Q = Nil then
  71.     L [LN] := P
  72.   else
  73.   begin
  74.     While Q^.Link <> Nil do
  75.       Q := Q^.Link;
  76.     Q^.Link := P;
  77.   end;
  78. end;
  79.  
  80.  
  81. Procedure Refill (Var A : AType; Var L : LType);
  82. Var
  83.   I, J : Integer;
  84.   P    : Ptr;
  85. begin
  86.   J := 1;
  87.   For I := 0 to 9 do
  88.   begin
  89.     P := L [I];
  90.     While P <> Nil do
  91.     begin
  92.       A [J] := P^.Info;
  93.       P := P^.Link;
  94.       J := J + 1;
  95.     end;
  96.   end;
  97.   For I := 0 to 9 do
  98.     L [I] := Nil;
  99. end;
  100.  
  101. Procedure RadixSort (Var A : AType; MaxData : Integer);
  102. Var
  103.   L        : LType;
  104.   I,
  105.   divisor,
  106.   ListNo,
  107.   Number   : Integer;
  108. begin
  109.   For I := 0 to 9 do L [I] := Nil;
  110.   divisor := 1;
  111.   While divisor <= 1000 do
  112.   begin
  113.     I := 1;
  114.     While I <= MaxData do
  115.     begin
  116.       Number := A [I];
  117.       ListNo := Number div divisor MOD 10;
  118.       Insert (L, Number, ListNo);
  119.       I := I + 1;
  120.     end;
  121.     Refill (A, L);
  122.     divisor := 10 * divisor;
  123.   end;
  124. end;
  125.  
  126. begin
  127.     ReadData (Ran, MaxData);
  128.     Writeln ('Unsorted : ');
  129.     WriteArray (Ran, MaxData);
  130.     RadixSort (Ran, MaxData);
  131.     Writeln ('Sorted   : ');
  132.     WriteArray (Ran, MaxData);
  133. end.
  134.