Radix Sort in data Structure

• Radix sort in data structure is a sorting algorithm that sort integer by processing individual digits by comparing individual digits sharing the same significant position.
• It is one of the linear sorting algorithm for integer.
• Sorting of numbers by this algorithm proceed by sorting the least significant to most significant digits for sorting.
• For radix sort element in this group to be sorted in the fixed range of 0 to 3.

Disadvantage of radix sort :

• One problem in this algorithm is that it depend on a large radix or a small radix makes the length of item to be sorted larger thus making the length of the items more significant than the number.
• Large radix require more memory if a large amount of memory is available then this algorithm is extremely fast.

Radix Sort Algorithm in Data Structure

1. for i $\gets$ 1 to d
2. do use a stable sort Algorithm to sort Array A on digit i.

This procedure assume that each element in a array A has (d) digits where digit one is least significant and (d) is most significant digit.

Radix Sort Example Step-By-Step

Question : < 326, 453, 608, 835, 751, 435, 704, 690 >

326, 453, 608, 835, 751, 435, 704, 690

Step-1 : 690, 751, 453, 704, 835, 435, 326, 608

Step-2: 704, 608, 326, 835, 435, 751, 453, 690

Step -3 : 326, 435, 453, 608, 690, 704, 751, 835

Time Complexity Analysis of Radix Sort

The running time depend on the intermediate stable sort algorithm .When each digit is in the range of (0 to k-1) and k is not too large counting sort is a good choice and in this case each pass over n d-digit number takes $\theta$ (n + k) time. Where k is range of integer and n is time. Where (d) passes total running time will be $\theta$ (d n + k d) .

T(n) =$ \theta$ (d(n + k))

where , k is number of buckets and n is number of elements to be sorted

and d is digits or maximum length of elements