Sorting is a common problem in computer science, and there are many algorithms that have been developed to solve it. One such algorithm is Radix Sort Algorithm, which is a non-comparative sorting algorithm that works by sorting numbers by their individual digits. It has a time complexity of O(n*k), where n is the number of elements to be sorted, and k is the number of digits in the largest number
.
Radix Sort works by sorting the numbers based on the least significant digit first and then moving on to the more significant digits. This is done by grouping the numbers based on their individual digits and then concatenating the groups in the order of their digits. The process is repeated for each digit until all digits have been considered.
Let’s take a look at the implementation of Radix Sort in C++, Java, and Python.
C++ Implementation of Radix Sort:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void radixSort(vector<int>& nums) {
int maxNum = *max_element(nums.begin(), nums.end());
int exp = 1;
vector<int> temp(nums.size());
while (maxNum / exp > 0) {
vector<int> count(10);
for (int i = 0; i < nums.size(); i++) {
count[(nums[i] / exp) % 10]++;
}
for (int i = 1; i < count.size(); i++) {
count[i] += count[i - 1];
}
for (int i = nums.size() - 1; i >= 0; i--) {
temp[count[(nums[i] / exp) % 10] - 1] = nums[i];
count[(nums[i] / exp) % 10]--;
}
for (int i = 0; i < nums.size(); i++) {
nums[i] = temp[i];
}
exp *= 10;
}
}
int main() {
vector<int> nums = { 170, 45, 75, 90, 802, 24, 2, 66 };
radixSort(nums);
for (int num : nums) {
cout << num << " ";
}
return 0;
}
In this implementation, we first find the maximum number in the array to determine the number of digits in the largest number. We then loop through each digit, starting with the least significant digit, and sort the numbers based on that digit using a counting sort. The sorted numbers are then stored in a temporary array, and the process is repeated for each digit.
Java Implementation of Radix Sort:
import java.util.Arrays;
public class RadixSort {
public static void radixSort(int[] nums) {
int maxNum = Arrays.stream(nums).max().getAsInt();
int exp = 1;
int[] temp = new int[nums.length];
while (maxNum / exp > 0) {
int[] count = new int[10];
for (int i = 0; i < nums.length; i++) {
count[(nums[i] / exp) % 10]++;
}
for (int i = 1; i < count.length; i++) {
count[i] += count[i - 1];
}
for (int i = nums.length - 1; i >= 0; i--) {
temp[count[(nums[i] / exp) % 10] - 1] = nums[i];
count[(nums[i] / exp) % 10]--;
}
System.arraycopy(temp, 0, nums, 0, nums.length);
exp *= 10;
}
}
public static void main(String[] args) {
int[] nums = { 170, 45, 75, 90, 802, 24, 2, 66 };
radixSort(nums);
for (int num : nums) {
System.out.print(num + " ");
}
}
}
In this Java implementation, we first find the maximum number in the array to determine the number of digits in the largest number. We then loop through each digit, starting with the least significant digit, and sort the numbers based on that digit using a counting sort. The sorted numbers are then stored in a temporary array, and the process is repeated for each digit.
Python Implementation of Radix Sort:
def radixSort(nums):
maxNum = max(nums)
exp = 1
temp = [0] * len(nums)
while maxNum // exp > 0:
count = [0] * 10
for num in nums:
count[(num // exp) % 10] += 1
for i in range(1, len(count)):
count[i] += count[i - 1]
for i in range(len(nums) - 1, -1, -1):
temp[count[(nums[i] // exp) % 10] - 1] = nums[i]
count[(nums[i] // exp) % 10] -= 1
nums[:] = temp[:]
exp *= 10
nums = [170, 45, 75, 90, 802, 24, 2, 66]
radixSort(nums)
print(nums)
In this Python implementation, we first find the maximum number in the array to determine the number of digits in the largest number. We then loop through each digit, starting with the least significant digit, and sort the numbers based on that digit using a counting sort. The sorted numbers are then stored in a temporary array, and the process is repeated for each digit.
Explanation of passes:
In each pass of the algorithm, we sort the numbers based on a different digit. The first pass sorts the numbers based on the least significant digit, while the last pass sorts the numbers based on the most significant digit. The complexity of each pass depends on the number of digits being considered, with the first pass being the simplest and each subsequent pass becoming increasingly complex.
The Python implementation uses Python’s built-in max() function to find the maximum number in the array, which may not be the most efficient approach for very large arrays. However, this implementation is very readable and easy to understand.
Overall, Radix Sort is a non-comparative sorting algorithm that sorts numbers based on their individual digits. It has a time complexity of O(n*k), where n is the number of elements to be sorted, and k is the number of digits in the largest number. Radix Sort can be implemented using a counting sort, and the complexity of each pass depends on the number of digits being considered. The algorithm can be implemented in C++, Java, Python, and other programming languages.
In each pass of the algorithm, we sort the numbers based on a different digit. The first pass sorts the numbers based on the least significant digit, while the last pass sorts the numbers based on the most significant digit. The complexity of each pass depends on the number of digits being considered, with the first pass being the simplest and each subsequent pass becoming increasingly complex.
In the C++, Java, and Python implementations above, we can see that the complexity of each pass is O(n), where n is the number of elements to be sorted. However, the total time complexity of the algorithm is O(nk), where k is the number of digits in the largest number. This is because the algorithm needs to loop through each digit k times to complete the sorting process.
Conclusion
In conclusion, Radix Sort is a non-comparative sorting algorithm that sorts numbers based on their individual digits. It has a time complexity of O(nk), where n is the number of elements to be sorted, and k is the number of digits in the largest number. It can be implemented using a counting sort, and the complexity of each pass depends on the number of digits being considered. The algorithm can be implemented in C++, Java, Python, and other programming languages.
