Radix Sort

Radix Sort

In computer science, radix sort is a non-comparative integer sorting algorithm that sorts data with integer keys by grouping keys by the individual digits which share the same significant position and value. A positional notation is required, but because integers can represent strings of characters (e.g., names or dates) and specially formatted floating point numbers, radix sort is not limited to integers. Radix sort dates back as far as 1887 to the work of Herman Hollerith on tabulating machines.

Radix sort
Class	Sorting algorithm
Data structure	Array
Worst case performance
Worst case space complexity

Example

 Sequence of values in each bucket during radix sort

Bucket	Pass 1	Pass 2	Pass 3
0	730	301	78
1	301	415	146
2	852	624, 426	269
3	593	730	301
4	624	146	415, 426
5	415	852	593
6	426, 146	269	624
7	987	78	730
8	78	987	852
9	269	593	987

Sorted list is 78,146,269,301,415,426,593,624,730,852,987

Algorithm

Radix (item [], N) /* item is an array of size N */
{
/*Q is an array of Circular Queue of size 10;*/
Initialize array Q; 
Find out the maximum element among the elements of the input array; 
Count the digit of the maximum element and store the value into pass;
Initialize div by 1;
For (I=1; I<=pass; I++)
{
/*inserting the elements into queue*/
For (J=0; J<N; J++) 
{
Set remainder is equals to item [J] %( div*10);
Update remainder by (remainder/div);
Insert (&Q [remainder], item [J]);
}
Update div by (div*10);
/*deleting the elements from the queue and place them into the array*/
For (J=0, index=0; J<10; J++) While (! Isempty (&Q [J])) item [index++] = Delete (&Q [J]);
}
}