Radix sort Algorithm
Radix sort is a non-comparative sorting algorithm that sorts data by grouping individual digits or characters of the input elements according to their place value.
It can be used to sort data such as numbers, strings, or even images, and it has a linear time complexity of O(nk), where n is the number of elements and k is the maximum number of digits or characters in the input.
The radix sort algorithm works by first sorting the input elements based on their least significant digit or character, then sorting them again based on the next most significant digit or character, and so on until all digits or characters have been considered.
Each pass of the algorithm creates a new distribution of the input elements, and this process is repeated until the elements are fully sorted.
Radix sort is often used for sorting large sets of data that have a large range of values, or for sorting data that cannot be compared using standard comparison operators.
However, it may not be as efficient as other sorting algorithms for small sets of data, and it requires extra memory to store the intermediate results of each pass.
Here’s an example of pseudocode
1. Start
2. Get an array of integers to be sorted
3. Find the maximum number in the array
4. Set the place value to 1
5. Loop while the place value is less than or equal to the maximum number:
a. Create 10 empty buckets
b. For each number in the array:
i. Get the digit in the current place value
ii. Add the number to the corresponding bucket based on the digit
c. Combine all the buckets into a new array
d. Set the array to the new sorted array
e. Multiply the place value by 10
6. Return the sorted array
7. End
In this pseudocode, we start by getting an array of integers to be sorted. We find the maximum number in the array to determine the number of digits to sort. We then start with the least significant digit and work our way up to the most significant digit.
For each place value, we create 10 empty buckets to hold the numbers with that digit in that place value. We then iterate through the array of numbers, getting the digit in the current place value for each number, and adding the number to the corresponding bucket.
We then combine all the buckets into a new array and repeat the process with the next place value until all digits have been considered.
Finally, we return the sorted array. Note that this pseudocode assumes the input array consists of non-negative integers, but the algorithm can be modified to handle negative numbers and other data types.
Radix Sort Code in Python
def radix_sort(nums):
max_num = max(nums)
place = 1
while max_num // place > 0:
buckets = [[] for _ in range(10)]
for num in nums:
digit = (num // place) % 10
buckets[digit].append(num)
nums = [num for bucket in buckets for num in bucket]
place *= 10
return nums
Explanation
In this implementation, nums is the list of integers to be sorted. We first find the maximum number in the list and use that to determine the number of digits to sort. We start with the least significant digit and loop through all digits up to the most significant digit.
For each place value, we create 10 empty buckets to hold the numbers with that digit in that place value. We then iterate through the list of numbers, getting the digit in the current place value for each number, and adding the number to the corresponding bucket. We then combine all the buckets back into a single list.
After each pass through the loop, we multiply place by 10 to move to the next place value. The process continues until we have processed all digits.
Finally, we return the sorted list. Note that this implementation assumes the input list consists of non-negative integers, but the algorithm can be modified to handle negative numbers and other data types.
C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void radix_sort(vector<int>& nums) {
int max_num = *max_element(nums.begin(), nums.end());
int place = 1;
while (max_num / place > 0) {
vector<vector<int>> buckets(10);
for (int num : nums) {
int digit = (num / place) % 10;
buckets[digit].push_back(num);
}
nums.clear();
for (vector<int>& bucket : buckets) {
nums.insert(nums.end(), bucket.begin(), bucket.end());
}
place *= 10;
}
}
int main() {
vector<int> nums = {170, 45, 75, 90, 802, 24, 2, 66};
radix_sort(nums);
for (int num : nums) {
cout << num << " ";
}
cout << endl;
return 0;
}
PHP
function radix_sort(&$nums) {
$max_num = max($nums);
$place = 1;
while ($max_num / $place > 0) {
$buckets = array_fill(0, 10, []);
foreach ($nums as $num) {
$digit = floor(($num / $place) % 10);
array_push($buckets[$digit], $num);
}
$nums = array_merge(...$buckets);
$place *= 10;
}
}
$nums = array(170, 45, 75, 90, 802, 24, 2, 66);
radix_sort($nums);
foreach ($nums as $num) {
echo $num . " ";
}
