Radix Sort

Radix Sort

Classical algorithms usually sort decimal numbers. In binary mode those algorithms don’t work well. Radix sort has been developed to improve the sort performance. This algorithm doesn’t use any control expression.

The Algorithm

Pascal Source Code

PROGRAM RADIX_SORT;
USES crt;
VAR
   i,j,k,m,l,n,t,p:integer;
   b,a,s:array[1..50] of integer;
   LA:array[1..50,1..50] of integer;
BEGIN
     clrscr;
     writeln('-----------------------------------------------------------');
     writeln('This program sorts a set of binary numbers using radix sort');
     writeln('algorithm without any control expression');
     writeln('-----------------------------------------------------------');
     write('How many numbers will be sorted? ');
     readln(p);
     write('Enter max. binary number of digits:');
     readln(n);
     for i:=1 to n do
         LA[1,i]:=1;
     writeln('Enter the binary numbers below in matrix format:');
     writeln('NOTE : Put spaces between binary numbers(ex:1 0 0 1 0 1)...!');
     for i:=2 to p+1 do
      begin
         for j:=1 to n do
             read(LA[i,j]);
         readln;
      end;
     for i:=1 to p+2 do
         a[i]:=i;
     for i:=n downto 1 do
      begin
           b[1]:=1;
           k:=1;
           m:=1;
           for j:=1 to p+1 do
            begin
                 l:=LA[a[j],i];
                 k:=k+l;
                 m:=m-l+1;
                 b[k]:=a[j+1];
                 s[m]:=a[j+1];
            end;
           for j:=1 to k-1 do
               a[j]:=b[j];
           t:=1;
           for j:=k to p+1 do
            begin
                 a[j]:=s[t];
                 t:=t+1;
            end;
      end;
     writeln('Here is the sorted binary numbers...');
     for i:=2 to p+1 do
      begin
           for j:=1 to n do
               write(LA[a[i],j]:2);
           writeln;
      end;
     for i:=2 to p+1 do
         a[i]:=a[i]-1;
     writeln('And here is the Indice:');
     for i:=2 to p+1 do
         writeln(a[i]);
     readln;
END.

Sample Execution

-----------------------------------------------------------

This program sorts a set of binary numbers using radix sort

algorithm without any control expression

-----------------------------------------------------------

How many numbers will be sorted? 5

Enter max. binary number of digits:8

Enter the binary numbers below in matrix format:

NOTE : Put spaces between binary numbers(ex:1 0 0 1 0 1)...!

1 0 0 1 1 1 0 1

1 0 1 0 1 0 1 1

0 0 0 0 1 1 1 1

1 1 0 0 1 1 0 0

0 0 0 0 0 1 1 0

'Here is the sorted binary numbers...

1 1 0 0 1 1 0 0

1 0 1 0 1 0 1 1

1 0 0 1 1 1 0 1

0 0 0 0 1 1 1 1

0 0 0 0 0 1 1 0

And here is the Index: