## Radix sort in an intuitive non-comparative integer title sorting algorithm Radix sort puts the elements in order by comparing the individual digits of the numbers which share the same significant position and value. Radix sort processes the digits either by Least Significant Digit (LSD) method or by Most Significant Digit (MSD) method.

#### The algorithm of Radix sort follows the following pattern :

- Receive an unsorted array of integer, often referred/represent a key.
- Iterate from most to least (or least to most) significant digits.
- Each iteration sort all of the values of the current significant digit the array.

#### There are two classification of Radix sorting :

- LSD Radix sort.
- MSD Radix sort.

MSD radix sorts use lexicographic order, which is suitable for sorting strings, such as words, or fixed-length integer representations. A sequence such as "b, c, d, e, f, g, h, i, ba" would be lexicographically sorted as "b, ba, c, d, e, f, g, h, i". And for variable –length integer representation, A sequence as “ 2,9,3,4,7,5,6,1,8,10”and after sorting the sequence 1,10, 2, 3, 4, 5, 6, 7, 8, 9 .

Suppose we have 9 numbers:

**493 812 715 710 195 437 582 340 385**

**195 340 385 437 493 582 710 715 812**

Notice that the numbers were added onto the list in the order that they were found, which is why the numbers appear to be unsorted in each of the sub lists above. Now, we gather the sub lists (in order from the 0 sub list to the 9 sub list) into the main list again:

**340 710 812 582 493 715 195 385 437**

Now, the sub lists are created again, this time based on the ten's digit:

Now the sub lists are gathered in order from 0 to 9:

**710 812 715 437 340 582 385 493 195**

At last, the list is gathered up again:

**195 340 385 437 493 582 710 715 812**

The C Code using LSD Radix sort Algorithm is below:

Radix Sort is very simple, and a computer can do it fast. When it is programmed properly, Radix Sort is in fact one of the fastest sorting algorithms for numbers or strings of letters. But sometimes it does not sort in place. Running Time of Radix sort is: O (d (n+k)), where n is the number of elements and k is the number of bits per element and d is digit.

## Post a Comment