What is the Radix Sort Algorithm in Data Structures | Data Structures Tutorial
What is the Radix Sort Algorithm in Data Structures | Data Structures Tutorial
In this article, you will understand the Radix sort Algorithm in better detail.
Radix sort is a sorting algorithm that is used in sorting the elements by first grouping every digit of the same place value. Afterward, sort the elements according to their increasing/decreasing order.
Assume an array of 8 elements. We have to sort the elements based on the value of the unit place. Now, we will sort the elements based on the value of the tenth place. This process goes on until the last significant index. In this counting, sort is used as an intermediate sort in the radix sort.
Working on Radix Sort
- Find the max element in the array, and call it max. Let Y be the number of digits in max. Y is calculated because we have to go through all the significant indexes of all elements.
- Go through each particular index one by one. Use any particular sorting techniques to sort the digits at each significant index. We use counting sort for this. Sort the elements based on the unity place digits (X=0).
- In this., sort the array elements on digits at tens place.
- Finally, sort the elements of the array based on the digits at the hundreds place.
Radix Sort Algorithm
radix_sort(array)
d <- find the maximum number of elements in the largest element
create d buckets of size 0-9
for i <- 0 to d
sort the array elements according to ith place digits using counting_sort
counting_sort(array, size)
large <- figure maximum value element in the array
initialize count array with all zeros
for i <- 0 to size
put the total count of each unique element and keep the count
at ith index in count array
for j <- 1 to large
find the cumulative sum and keep it in count array i.
for j <- size to 1
restore the elements to the array until the count is decreased to 1.
Complexity
Time complexity
The best case complexity is O(n+k), the average case complexity is O(n+k), and the worst case complexity is O(n+k).
Space complexity is O(max)
Radix sort is a non-comparative algorithm, it has advantages over comparative sorting algorithms.
Applications of Radix Sort Algorithm
- It is used when using the DC3 algorithm while making a suffix array.
- It is used in the implementation of places where there are numbers in large ranges.