Radix sort algorithm is a non-comparative sorting algorithm in computer science. It avoids comparison by creating and categorizing elements based on their radix. For elements with more than one significant digit, it repeats the bucketing process for each digit while preserving the previous step's ordering until all digits have been considered.
Radix sort and bucket sort are almost equivalent; bucket sort goes from MSD to LSD, while radix sort is capable of both "direction" (LSD or MSD). Here you can take a look at Bucket Sort Algorithm Time Complexity, Pseudocode and Applications.
What Is a Radix Sort Algorithm?
- Radix Sort is a linear sorting algorithm.
- Radix Sort's time complexity of O(nd), where n is the size of the array and d is the number of digits in the largest number.
- It is not an in-place sorting algorithm because it requires extra space.
- Radix Sort is a stable sort because it maintains the relative order of elements with equal values.
- Radix sort algorithm may be slower than other sorting algorithms such as merge sort and Quicksort if the operations are inefficient. These operations include sub-inset lists and delete functions, and the process of isolating the desired digits.
- Because it is based on digits or letters, radix sort is less flexible than other sorts. If the type of data changes, the Radix sort must be rewritten.
After defining the radix sort algorithm, you will look at how it works with an example.
Working of Radix Sort Algorithm
- The Radix sort algorithm works by ordering each digit from least significant to most significant.
- In base 10, radix sort would sort by the digits in the one's place, then the ten's place, and so on.
- To sort the values in each digit place, Radix sort employs counting sort as a subroutine.
- This means that for a three-digit number in base 10, counting sort will be used to sort the 1st, 10th, and 100th places, resulting in a completely sorted list. Here's a rundown of the counting sort algorithm.
Assume you have an 8-element array. First, you will sort the elements by the value of the unit place. It will then sort the elements based on the value of the tenth position. This process is repeated until it reaches the last significant location.
Let's start with [132, 543, 783, 63, 7, 49, 898]. It is sorted using radix sort, as illustrated in the figure below.
- Find the array's largest element, i.e., maximum. Consider A to be the number of digits in maximum. A is calculated because we must traverse all of the significant locations of all elements.
The largest number in this array [132, 543, 783, 63, 7, 49, 898] is 898. It has three digits. As a result, the loop should be extended to hundreds of places (3 times).
- Now, go through each significant location one by one. Sort the digits at each significant place with any stable sorting technique. You must use counting sort for this. Sort the elements using the unit place digits (A = 0).
- Sort the elements now by digits in the tens place.
- Finally, sort the elements by digits in the hundreds place.
In this tutorial, you will look at the pseudocode for the radix sort algorithm.
Pseudocode of Radix Sort Algorithm
|
Radix_Sort(Array, p) // p is the number of passes for j = 1 to p do int count_array[10] = {0}; for i = 0 to n do count_array[key of(Array[i]) in pass j]++ // count array stores the count of key for k = 1 to 10 do count_array[k] = count_array[k] + count_array[k-1] for i = n-1 downto 0 do result_array[ count_array[key of(Array[i])] ] = Array[j] //Construct the resulting array (result_array) by checking //new Array[i] position from count_array[k] count_array[key of(Array[i])]-- for i=0 to n do Array[i] = result_array[i] //The main array Array[] now contains sorted numbers based on the current digit position. the end for(j) end function |
After understanding the pseudocode of the radix sort algorithm, you will now examine its performance in this tutorial.
Performance of Radix Sort Algorithm
The Time Complexity of Radix Sort Algorithm
Worst-Case Time Complexity
In radix sort, the worst case is when all elements have the same number of digits except one, which has a significantly large number of digits. If the number of digits in the largest element equals n, the runtime is O. (n2).
Best Case Time Complexity
When all elements have the same number of digits, the best-case scenario occurs. O(a(n+b)) is the best-case time complexity. If b equals O(n), the time complexity is O. (a*n).
Average Case Time Complexity
You considered the distribution of the number of digits in the average case. There are 'p' passes, and each digit can have up to 'd' different values. Because radix sort is independent of the input sequence, we can keep n constant.
T(n) = p(n+d) is the running time of radix sort. Using the linearity of expectation and taking into account both sides' expectations.
Radix sort has an average case time complexity of O(p*(n+d)).
The Space Complexity of Radix Sort Algorithm
Because Radix sort employs Counting sort, which uses auxiliary arrays of sizes n and k, where n is the number of elements in the input array and k is the largest element among the dth place elements (ones, tens, hundreds, and so on) of the input array. Hence, the Radix sort has a space complexity of (n+k).
Stability of Radix Sort Algorithm
Radix Sort algorithm is a stable sorting subroutine-based integer sorting algorithm. It is a sorting algorithm that does not use comparisons to sort a collection of integers. It classifies keys based on individual digits with the same significant position and value.
Moving forward in this tutorial, you will look at some of its benefits and drawbacks.
Advantages Radix Sort Algorithm
Following are some advantages of the radix sorting algorithm:
- Fast when the keys are short, i.e. when the array element range is small.
- Used in suffix arrays construction algorithms such as Manber's and the DC3 algorithm.
- Radix Sort is a stable sort because it maintains the relative order of elements with equal values.
Disadvantages of Radix Sort Algorithm
Following are some disadvantages of the radix sorting algorithm:
- The Radix Sort algorithm is less flexible than other sorts because it is based on digits or letters. As a result, for each different type of data, it must be rewritten.
- Radix sort has a higher constant than other sorting algorithms.
- It takes up more space than Quicksort, which is used for in-place sorting.
- Radix sort may be slower than other sorting algorithms such as merge sort and Quicksort if the operations are inefficient. These operations include sub-inset lists and delete functions, as well as the process of isolating the desired digits.
- Because it is based on digits or letters, the radix sort is less flexible than other sorts. If the data type must be rewritten, so must the Radix sort.
Now that you have explored the benefits and drawbacks of the radix sort algorithm, look at some of its applications.
Applications of Radix Sort Algorithm
These are some applications of radix sort:
- The Radix sort algorithm is used in a typical computer, a sequential random-access machine, multiple fields key records.
- While creating a suffix array, use the DC3 algorithm (Kärkkäinen-Sanders-Burkhardt).
- The Radix sort algorithm locates locations where there are numbers in extensive ranges.
Finally, in this tutorial, you will look at the code implementation of the radix sort algorithm.
Code Implementation of Radix Sort Algorithm
|
#include<stdio.h> #include<conio.h> #include<stdlib.h> int Max_value(int Array[], int n) // This function gives maximum value in array[] { int i; int maximum = Array[0]; for (i = 1; i < n; i++){ if (Array[i] > maximum) maximum = Array[i]; } return maximum; } void radixSortalgorithm(int Array[], int n) // Main Radix Sort sort function { int i,digitPlace = 1; int result_array[n]; // resulting array int largest = Max_value(Array, n); // Find the largest number to know number of digits while(largest/digitPlace >0){ int count_array[10] = {0}; for (i = 0; i < n; i++) //Store the count of "keys" or digits in count[] count_array[ (Array[i]/digitPlace)%10 ]++; for (i = 1; i < 10; i++) count_array[i] += count_array[i - 1]; for (i = n - 1; i >= 0; i--) // Build the resulting array { result_array[count_array[ (Array[i]/digitPlace)%10 ] - 1] = Array[i]; count_array[ (Array[i]/digitPlace)%10 ]--; } for (i = 0; i < n; i++) // numbers according to current digit place Array[i] = result_array[i]; digitPlace *= 10; // Move to next digit place } } void displayArray(int Array[], int n) // Function to print an array { int i; for (i = 0; i < n; i++) printf("%d ", Array[i]); printf("\n"); } int main() { int array1[] = {20,30,40,90,60,100,50,70}; int n = sizeof(array1)/sizeof(array1[0]); printf("Unsorted Array is : "); displayArray(array1, n); radixSortalgorithm(array1, n); printf("Sorted Array is: "); displayArray(array1, n); return 0; } |
Output
Next Steps
In this tutorial, you learned about the radix sort algorithm and its working process with an example and some applications of the radix sort algorithm.
If you're searching for a more extensive study that goes beyond Data Structure and covers the most in-demand programming languages and abilities today, then Simplilearn’s Post Graduate Program in Full Stack Web Development is for you.
Do you have any questions about this tutorial on the radix sort algorithm? If you do, please leave them in the comments section at the bottom of this page. Our specialists will respond to your questions as quickly as possible!
