What is Radix Sort
Radix sort is a sorting algorithm that works by comparing the digits of numbers. It's like sorting a bunch of phone numbers by area code first, and then by the rest of the digits.
Here's an example: Let's say you have the numbers 12, 23, 45, 67, and 89. To sort them using radix sort, you start by looking at the least significant digit (the rightmost digit) of each number. You group the numbers based on that digit, so you end up with two groups: one group with numbers ending in 2, and another group with numbers ending in 3, 5, 7, and 9. You then take the numbers in each group and sort them based on the next least significant digit (the tens place), so you end up with four groups: one with numbers starting with 2, one with numbers starting with 3, one with numbers starting with 4 or 6, and one with numbers starting with 5 or 8. You repeat this process, sorting based on each digit position until the numbers are sorted in ascending order.
Radix sort is a bit more complex than some other sorting algorithms, but it can be very efficient for certain types of data, particularly when the range of possible values is known in advance.
Who invented it?
The radix sort algorithm was invented by the American computer scientist Herman Hollerith in the late 19th century. Hollerith was working on ways to tabulate and analyze data for the U.S. Census, and he developed a machine called the tabulating machine that used punch cards to store and sort data. The radix sort algorithm was a key part of this machine's sorting process, and it helped to revolutionize the field of data processing.
Since then, the radix sort algorithm has been refined and improved by many other computer scientists, and it remains an important sorting algorithm today, especially in applications that involve large amounts of data with known integer ranges.
Pseudocode
radix_sort(list)
// Find the maximum number in the list to determine the number of digits.
max_num = maximum(list)
num_digits = count_digits(max_num)
// Iterate through each digit, starting with the least significant digit.
for i = 0 to num_digits - 1
// Create 10 empty buckets for each possible digit (0-9).
buckets = array of 10 empty lists
// Put each number in the list into the appropriate bucket based on its current digit.
for number in list
digit = get_digit(number, i)
buckets[digit].add(number)
// Concatenate the lists in order to get the new sorted list.
list = concatenate(buckets)
return list
In this pseudocode, maximum(list) is a function that returns the maximum number in the list, count_digits(num) is a function that returns the number of digits in a number num, get_digit(num, i) is a function that returns the i-th digit of a number num (counting from the rightmost digit), and concatenate(buckets) is a function that concatenates all the lists in the buckets array in order.
Sample Code
// C++ code snippet
// Get the maximum number in the array
int getMax(vector arr) {
int max_num = arr[0];
for (int i = 1; i < arr.size(); i++) {
if (arr[i] > max_num) {
max_num = arr[i];
}
}
return max_num;
}
// Count the number of digits in a number
int countDigits(int num) {
int count = 0;
while (num != 0) {
num /= 10;
count++;
}
return count;
}
// Get the i-th digit of a number (counting from the rightmost digit)
int getDigit(int num, int i) {
for (int j = 0; j < i; j++) {
num /= 10;
}
return num % 10;
}
// Perform radix sort on the array
void radixSort(vector& arr) {
int max_num = getMax(arr);
int num_digits = countDigits(max_num);
for (int i = 0; i < num_digits; i++) {
// Create 10 empty buckets for each possible digit (0-9).
vector> buckets(10);
// Put each number in the array into the appropriate bucket based on its current digit.
for (int j = 0; j < arr.size(); j++) {
int digit = getDigit(arr[j], i);
buckets[digit].push_back(arr[j]);
}
// Concatenate the lists in order to get the new sorted array.
arr.clear();
for (int j = 0; j < 10; j++) {
arr.insert(arr.end(), buckets[j].begin(), buckets[j].end());
}
}
}
int main() {
// Example usage
vector arr = {170, 45, 75, 90, 802, 24, 2, 66};
radixSort(arr);
for (int i = 0; i < arr.size(); i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
# Python code snippet
def radix_sort(arr):
max_num = max(arr)
num_digits = len(str(max_num))
for i in range(num_digits):
# Create 10 empty buckets for each possible digit (0-9).
buckets = [[] for _ in range(10)]
# Put each number in the array into the appropriate bucket based on its current digit.
for j in range(len(arr)):
digit = int(str(arr[j])[i]) if i < len(str(arr[j])) else 0
buckets[digit].append(arr[j])
# Concatenate the lists in order to get the new sorted array.
arr = [elem for sublist in buckets for elem in sublist]
return arr
# Example usage
arr = [170, 45, 75, 90, 802, 24, 2, 66]
arr_sorted = radix_sort(arr)
print(arr_sorted)
import java.util.Arrays;
public class RadixSort {
public static int[] radixSort(int[] arr) {
int max_num = Arrays.stream(arr).max().getAsInt();
int num_digits = (int) Math.log10(max_num) + 1;
for (int i = 0; i < num_digits; i++) {
// Create 10 empty buckets for each possible digit (0-9).
int[][] buckets = new int[10][arr.length];
int[] bucket_sizes = new int[10];
// Put each number in the array into the appropriate bucket based on its current digit.
for (int j = 0; j < arr.length; j++) {
int digit = getDigit(arr[j], i);
buckets[digit][bucket_sizes[digit]++] = arr[j];
}
// Concatenate the lists in order to get the new sorted array.
int index = 0;
for (int j = 0; j < 10; j++) {
for (int k = 0; k < bucket_sizes[j]; k++) {
arr[index++] = buckets[j][k];
}
}
}
return arr;
}
private static int getDigit(int num, int i) {
return (num / (int) Math.pow(10, i)) % 10;
}
public static void main(String[] args) {
// Example usage
int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
int[] arr_sorted = radixSort(arr);
System.out.println(Arrays.toString(arr_sorted));
}
}