 Loading, please wait...  # What is the Radix Sort Algorithm in Data Structures | Data Structures Tutorial

Jan 15, 2023 DataSturctureTutorial, 652 Views

# What is the Radix Sort Algorithm in Data Structures | Data Structures Tutorial

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.

1. 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.
2. 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).
3. In this., sort the array elements on digits at tens place.
4. Finally, sort the elements of the array based on the digits at the hundreds place.

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.