Radix Sort in Data Structure

Radix sort is a sorting technique that isn’t based on comparison and groups the individual digits of the same place value before sorting the items. After that, arrange the items in increasing order or decreasing order. Let’s say we have an array of seven elements. We’ll start by sorting elements by the value of the unit place. Then we’ll sort the elements by the value of the tenth position. This process continues until the last significant location is reached. Elements of an array before applying radix sort are {101, 45, 543, 233, 321, 833, 432}. Our array will like this {101, 321, 432, 543, 233, 833, 45} after sorting the unit place digits. As an intermediate sort, Radix sort uses counting sort.

Working of Radix Sort

Let’s start with an example array having elements: [125, 436, 568, 27, 5, 49, 792].

1. Find the array’s largest element, i.e. max. Let X be the maximum number of digits. Because we must go over all of the significant positions of all elements, X is calculated. In the given array [125, 436, 568, 27, 5, 49, 792], we have the largest number 792. It has 3 digits. Therefore, the loop should go up to hundreds place (i.e., 3 times).

2. Now, go through each important location one by one. Sort the numerals at each significant place using any stable sorting strategy. For this, we applied a counting sort. Sort the elements by the digits in the unit position (X=0).

3. Sort the elements by digits in the tens place now.

4. Finally, sort the elements by the hundreds place digits.

Algorithm for Radix Sort

Step 1: As Max, find the highest number in ARR.

Step 2: Determine the number of digits in Max and set NOS = number of digits in Max.

Step 3: For PASS = 1; PASS = NOS, repeat Steps 4–8.

Step 4: Repeat Steps 5–7 for ARR sizes I=0 to I.

Step 5: SET DIGIT = Arr[I]

Step 6: At index DIGIT, add element Arr[I] to the sub array.

Step 7: Increase the number of sub arrays in the index DIGIT.

[LOOP ENDS]

Step 8: Using the index 0 as a starting point, choose elements from the sub array and place them in ARR.

[LOOP ENDS]

Step 9: FINISH

Analysis of Radix Sort for Complexity

Time Complexity

We already know that the Counting sort algorithm takes Θ(n+k) time, where n is the number of elements in the input array and k is the largest element among the dth place elements in the input array (ones, tens, hundreds, and so on). Counting sort is now called inside a ‘for loop’ that runs for d times, where d is the number of digits in the input array’s largest element (max). As a result, we can predict that Radix sort will take Θ(d( n+ k)). As a result, radix sort has a linear time complexity, which is superior to Ω(nlogn) for comparison-based sorting algorithms.

Space Complexity

Radix sort employs Counting sort, which uses auxiliary arrays of sizes n and k, where n is the number of items in the input array and k is the largest element among the {d}^{th} place members of the input array (ones, tens, hundreds, and so on) (note that this is not the largest element of the input array). As a result, the Radix sort has a space complexity of Ω(n+k).

Advantages of Radix Sort

1. Quick when the keys are short, i.e. when the array elements’ range is small.

2. Used in techniques for constructing suffix arrays, such as Manber’s algorithm and the DC3 algorithm.

Disadvantages of Radix Sort

1. Radix Sort is less versatile than other sorts because it relies on numbers or letters for its operation. As a result, it must be rewritten for each distinct type of data.

2. When compared to other sorting algorithms, the Radix sort has a higher constant.

3. When compared to Quicksort, which is in-place sorting, it takes up more space