Saturday, December 6, 2014

Radix Sort

Radix Sort::

Radix Sort is a non-comparative sorting algorithm.
It sorts the data with integer keys by grouping keys by the individual digits which share the same significant position and value.
For Example 11, 21 51, 61 will be put into single group because all are having the digit 1 in least significant position.


There are 2 types of Radix sort.
1. Least significant digit radix sorts
2. Most significant digit radix sorts

Least significant radix sort::

Lease significant digit is the last digit of the number.(For Example in 534, 4 is LSD)
For number of Digit in a Maximum_number(Numbers to be sorted)
1. Take the least significant digit of each number.
2. Grouping the numbers with the same digit into a single group.
3. Repeat the grouping process, starting with the next digit to the left.

Example LSD Radix Sort:

Most significant radix sort::

     Most significant digit is the first digit of the number.(For Example in 534, 5 is MSD)
These sort keys in lexicographic order, which is suitable for sorting strings, such as words, or fixed-length integer representations. Unlike LSD radix sort, this sort does not necessarily preserve the original order of duplicate keys. MSD radix sort starts processing the keys from most to least significant digit.

b c d e f g h i j ba would output as b ba c d e f g h i j
1 2 3 4 5 6 7 8 9 10 would output as 1 10 2 3 4 5 6 7 8 9
    1. Take the key’s most significant digit
    2. Sort based on that digit, grouping same digit elements into one group
    3. In each group, start with the next digit to the right and sort recursively
    4. Finally, concatenate the group in order
Note:: Recursive Loop Will stop when all group contains single value. and Print the values in each Group in same order.

Example MSD Radix Sort:

Points to Remember::


      2. Data Structures and Algorithm Analysis in C, 2nd Edition, Mark Allen Weiss

Goto Data Structure Concepts

No comments:

Post a Comment