Radix Sort
The sorting algorithm used in Radix Sort is arranging
the list digit by digit. Sorting starts from least significant digit to most
significant digit. First sort the list by the least significant bit while
preserving their relative order using a secure sort. Then we sort them by the
next bit, and so on from right to left, and the list will end up sorted. Most
often, the counting sort algorithm is used to accomplish the bitwise sorting,
since the number of values a bit can have is minimal - only '1' or '0'.
Original
List
150
|
123
|
2
|
23
|
55
|
68
|
150
|
123
|
002
|
023
|
055
|
068
|
The list
is sorted by least significant bits (unit place)
150
|
002
|
123
|
023
|
055
|
068
|
150
|
002
|
123
|
023
|
055
|
068
|
The list
is sorted tenth place
002
|
123
|
023
|
150
|
055
|
068
|
The list
is sorted hundred place
002
|
123
|
023
|
150
|
055
|
068
|
Final
List
002
|
023
|
055
|
068
|
123
|
150
|
Complexity
Running time for this example is:
·
T(n) = Ө (d(n+k))
·
k = number of buckets = 10(0 to 9).
·
n = number of elements to be sorted = 15
·
d = digits or maximum length of element = 2
·
Thus in our example, the algorithm will take
·
T(n) = Ө (d(n+k))
o = Ө (2(15+10))
o = Ө (50) execution time.
·
Computational complexity: classification is based
on worst, average and best behaviour of sorting a list of size (n).
Algorithm
void
radixsort(int a[],int n)
1.
int rear[10],front[10],first,p,q,exp,k,i,y,j;
2.
struct
3.
{
4.
int data;
5.
int next;
6.
}Temp[N];
7.
for i=0 to n step 1
8.
do
9.
Temp[i].data=a[i];
10.
Temp[i].next=i+1;
11.
endfor
12.
Temp[n-1].data=a[n-1];
13.
Temp[n-1].next=-1;
14.
first=0;
15.
for k=1 to 2 step 1
16.
do
17.
for i=0 to 9 step 1
18.
do
19.
front[i]=-1;
20.
rear[i]=-1;
21.
endfor
22.
while first!=-1
23.
do
24.
p=first;
25.
first=Temp[first].next;
26.
y=Temp[p].data;
27.
exp=pow(10,k-1);
28.
j=(y/exp)%10;
29.
q=rear[j];
30.
if q=-1)
31.
then
32.
front[j]=p;
33.
else
34.
Temp[q].next=p;
35.
endif
36.
rear[j]=p;
37.
enddo
38.
for j=0 to 10 and front[j]=-1
39.
endfor
40.
first=front[j];
41.
while j<=9
42.
do
43.
for i=i+1 to 10 and front[i]=-1
44.
endfor
45.
if i<=9
46.
then
47.
p=i;
48.
Temp[rear[j]].next=front[i]
49.
endif
50.
j=i;
51.
enddo
52.
Temp[rear[p]].next=-1;
53.
endfor
54.
for i=0 to n-1 step 1
55.
do
56.
a[i]=Temp[first].data;
57.
first=Temp[first].next;
58.
endfor
Pseudo Code
radixsort(int
a[],int n)
iniatilize
i,j,t,k;
i←1
define
array b[n][100], bc[n];
while
TRUE
do
for j←0 to n-1
do
bc[j] ←0;
end for j
for j←0 to n-1
do
t←a[j]/i;
while t>9
do
t←t/10;
end while
b[t][bc[t]] ←a[j];
bc[t]++;
end for j
if bc[0]==n
break;
t←0;
for j←0 to n-1
do
for k←0 to bc[j]
do
a[t]←b[j][k];
t++;
end for k
end for j
i¬i*10;
end while
Source Code
import
java.io.*;
class Radix_Sort
{
int Num[],Size;
void Input()
{
BufferedReader Br=new
BufferedReader(new InputStreamReader(System.in));
try
{
System.out.print("\tEnter
Size : ");
Size=Integer.parseInt(Br.readLine());
Num=new int[Size];
for(int i=0; i<Size;
i++)
{
System.out.print("\tEnter Element at ["+(i+1)+"] : "
);
Num[i]=Integer.parseInt(Br.readLine());
}
}
catch(Exception Ex){}
}
int MaximumNum()
{
int maxNum=Num[0];
for(int i=0; i<Size;
i++)
{
if(Num[i]>maxNum)
{
maxNum=Num[i];
}
}
int nDig=0;
while(maxNum>0)
{
nDig++;
maxNum=maxNum/10;
}
return nDig;
}
void Sort()
{
int mDig=MaximumNum();
for(int j=1; j<=mDig; j++)
{
int Numb2D[][]= new
int[10][20];
int cDig[]= new
int[10];
System.out.print("\n\tAfter Pass = "+j+" :
");
for(int i=0; i<Size;
i++)
{
int dig;
dig=Num[i]/(int)(Math.pow(10,j-1))%10;
Numb2D[dig][cDig[dig]++]=Num[i];
}
int k=0;
for(int i=0; i<10;
i++)
{
int m=0;
while(m<cDig[i])
{
Num[k++]=Numb2D[i][m++];
}
}
display();
}
}
void display()
{
for( int i=0;i<Size;
i++)
{
System.out.print(Num[i]+" ");
}
System.out.println();
}
public static void main(String
args[])
{
Radix_Sort RST =new
Radix_Sort();
RST.Input();
System.out.print("\n\tOriginal Array : ");
RST.display();
RST.Sort ();
System.out.print("\n\tSorted Array : ");
RST.display();
}
}
Output
Enter Size : 5
Enter Element at [1] : 123
Enter Element at [2] : 1234
Enter Element at [3] : 56
Enter Element at [4] : 78
Enter Element at [5] : 2
Original Array : 123 1234 56 78 2
After Pass = 1 : 2
123 1234 56 78
After Pass = 2 : 2
123 1234 56 78
After Pass = 3 : 2 56
78 123 1234
After Pass = 4 : 2 56
78 123 1234
Sorted Array : 2 56 78 123 1234
