[Back to SORTING SWAG index]  [Back to Main SWAG index]  [Original]

{
> I agree... unFortunately the Radix algorithm (which is a
> sophisticated modification of a Distribution Sort algorithm) is
> very Complex, highly CPU dependent and highly data dependent.

We must be speaking of a different Radix Sort.  Is the sort you are
talking about sort numbers on the basis of their digits?

> My understanding is that a Radix sort cannot be implemented in
> Pascal without using a majority of Asm (which means you might as
> well code the whole thing in Asm.)

> assembly) or dig up some working code, I would love to play With it!

************************************************************************
*                                                                      *
* Name : Joy Mukherjee                                                 *
* Date : Mar. 26, 1990                                                 *
* Description : This is the Radix sort implemented in Pascal           *
*                                                                      *
************************************************************************
}

Program SortStuff;

Uses Crt, Dos;

Type
    AType = Array [1..400] of Integer;
    Ptr   = ^Node;
    Node  = Record
          Info : Integer;
          Link : Ptr;
        end;
    LType = Array [0..9] of Ptr;

Var
   Ran     : AType;
   MaxData : Integer;

Procedure ReadData (Var A : AType; Var MaxData : Integer);

Var I : Integer;

begin
     MaxData := 400;
     For I := 1 to 400 do A [I] := Random (9999);
end;

Procedure WriteArray (A : AType; MaxData : Integer);

Var I : Integer;

begin
  For I := 1 to MaxData do
    Write (A [I] : 5);
  Writeln;
end;

Procedure Insert (Var L : LType; Number, LN : Integer);

Var
  P, Q : Ptr;

begin
  New (P);
  P^.Info := Number;
  P^.Link := Nil;
  Q := L [LN];
  if Q = Nil then
    L [LN] := P
  else
  begin
    While Q^.Link <> Nil do
      Q := Q^.Link;
    Q^.Link := P;
  end;
end;


Procedure Refill (Var A : AType; Var L : LType);
Var
  I, J : Integer;
  P    : Ptr;
begin
  J := 1;
  For I := 0 to 9 do
  begin
    P := L [I];
    While P <> Nil do
    begin
      A [J] := P^.Info;
      P := P^.Link;
      J := J + 1;
    end;
  end;
  For I := 0 to 9 do
    L [I] := Nil;
end;

Procedure RadixSort (Var A : AType; MaxData : Integer);
Var
  L        : LType;
  I,
  divisor,
  ListNo,
  Number   : Integer;
begin
  For I := 0 to 9 do L [I] := Nil;
  divisor := 1;
  While divisor <= 1000 do
  begin
    I := 1;
    While I <= MaxData do
    begin
      Number := A [I];
      ListNo := Number div divisor MOD 10;
      Insert (L, Number, ListNo);
      I := I + 1;
    end;
    Refill (A, L);
    divisor := 10 * divisor;
  end;
end;

begin
    ReadData (Ran, MaxData);
    Writeln ('Unsorted : ');
    WriteArray (Ran, MaxData);
    RadixSort (Ran, MaxData);
    Writeln ('Sorted   : ');
    WriteArray (Ran, MaxData);
end.

[Back to SORTING SWAG index]  [Back to Main SWAG index]  [Original]