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.
Example
