Radix sort
Let
a be an array of n numbers. Our aim is to sort this array in ascending order
using radix sort. The steps to be followed are
i)
Initialize ten queues namely q[0], q[1],
………, q[9]. That is set rear [i] = front [i] = NULL for all I = 0, 1, 2, ……,9.
ii)
Scan the array from left to right and
find the least significant digit for all array elements.
iii)
If it is 0, push the number in q[0]; if
it is 1, push the number in q[1],….., and if it is 9, push the number in q[9].
iv)
After pushing all the elements in the
respective queues, pop up the data from 0th queue to 9th
queue and restore in the array a.
v)
Again scan the array from left to right
and find the second least significant digit for all array elements.
vi)
Repeats steps (iii) and (iv)
The repetition of the
above process depends upon the width of the maximum element in the array. That is
if the maximum width of the array element is 3, then scan the array three times
and find the 1st least significant digit and 3rd least
significant digit.
Sort
the given array elements in ascending order. Suppose the numbers in the array
are
a[1]
= 252 a[2] = 570 a[3] = 480 a[4] = 377
a[5] = 120 a[6] = 902
i)
Initialize 10 queues
Rear[0] = front[0] =
NULL
Rear[1] = front[1] =
NULL
……………………………
……………………………
Rear[9] = front[9] = NULLii)
Procedure
radixsort ( a, n) // a- given array , n – size of the array
{
define queue q[10] ; // already
defined queue
max = a[1] ;
for i = 1 to n do // to find
the maximum
if ( max < a[i]) then // number in the array
max = a[i] ;
w = 0 ;
while ( max > 0) do // to find the width of the maximum number
{
max = max / 10 ;
w =w + 1 ;
}
for k = 1 to w do {
for I = 0 to n-1 do
{
l = (a[i] /
pow(10 , k-1)) % 10 ;
push (q[l] ,
a[i]) ;
}
j =0 ;
for i = 0 to
9 do // to restore the elements from
queue to array
{ while ( front[i] =
rear[i] = NULL)
{
a[j] = pop(q[i]) ;
j = j + 1 ;
}
}
}
}
No comments:
Post a Comment