Algorithm
Radix sort is a non-comparative sorting algorithm that works by distributing elements into buckets according to their individual digits. It is a linear time, linear space algorithm used for integer or string keys. Radix sort can be applied to numbers by considering each digit at a specific place value, starting from the least significant digit (LSD) to the most significant digit (MSD) or vice versa.
Here's a basic outline of how radix sort works:
-
Initialization: Determine the maximum number of digits in the input numbers. This is necessary to know the number of passes needed.
-
Passes: Perform a stable sort for each digit place, starting from the rightmost digit (LSD) or leftmost digit (MSD). For each pass, distribute the elements into buckets based on the digit at the current place value.
-
Collecting: After each pass, collect the elements from the buckets in the order they were placed. This ensures that the order of elements with the same digit at the current place value is preserved.
-
Repeat: Repeat the passes until all digits have been considered.
Code Examples
#1 Radix Sort implement in Python
Code -
Python Programming
def counting_sort(arr, exp):
n = len(arr)
output = [0] * n
count = [0] * 10
# Count occurrences of digits at the current place value
for i in range(n):
index = arr[i] // exp
count[index % 10] += 1
# Update count to store the position of the next occurrence
for i in range(1, 10):
count[i] += count[i - 1]
# Build the output array using the count array
i = n - 1
while i >= 0:
index = arr[i] // exp
output[count[index % 10] - 1] = arr[i]
count[index % 10] -= 1
i -= 1
# Copy the output array back to the original array
for i in range(n):
arr[i] = output[i]
def radix_sort(arr):
# Find the maximum number to determine the number of digits
max_num = max(arr)
exp = 1
# Apply counting sort to sort elements based on each digit
while max_num // exp > 0:
counting_sort(arr, exp)
exp *= 10
# Example usage
arr = [170, 45, 75, 90, 802, 24, 2, 66]
radix_sort(arr)
print("Sorted array:", arr)
#2 Radix Sort implement in Java
Code -
Java Programming
import java.util.Arrays;
public class RadixSort {
public static void radixSort(int[] arr) {
// Find the maximum number to know the number of digits
int max = getMax(arr);
// Do counting sort for every digit
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSort(arr, exp);
}
}
private static void countingSort(int[] arr, int exp) {
int n = arr.length;
int[] output = new int[n];
int[] count = new int[10];
// Initialize count array
Arrays.fill(count, 0);
// Store count of occurrences in count[]
for (int i = 0; i < n; i++) {
count[(arr[i] / exp) % 10]++;
}
// Change count[i] so that count[i] now contains the actual
// position of this digit in output[]
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
// Build the output array
for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
// Copy the output array to arr[], so that arr[] contains sorted numbers according to current digit
System.arraycopy(output, 0, arr, 0, n);
}
private static int getMax(int[] arr) {
int max = arr[0];
for (int value : arr) {
if (value > max) {
max = value;
}
}
return max;
}
public static void printArray(int[] arr) {
for (int value : arr) {
System.out.print(value + " ");
}
System.out.println();
}
public static void main(String[] args) {
int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
System.out.println("Original array:");
printArray(arr);
radixSort(arr);
System.out.println("Sorted array:");
printArray(arr);
}
}
#3 Radix Sort implement in C
Code -
C Programming
#include <stdio.h>
// Function to find the maximum number to determine the number of digits
int findMax(int arr[], int n) {
int max = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
// Using counting sort to sort the elements based on significant places
void countingSort(int arr[], int n, int exp) {
const int radix = 10; // The base of the number system
int output[n]; // Output array
int count[radix] = {0};
// Count the occurrences of each digit at the current significant place
for (int i = 0; i < n; i++) {
count[(arr[i] / exp) % radix]++;
}
// Adjust the count array to store the actual position of the digits in the output array
for (int i = 1; i < radix; i++) {
count[i] += count[i - 1];
}
// Build the output array by placing the elements in their sorted order
for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % radix] - 1] = arr[i];
count[(arr[i] / exp) % radix]--;
}
// Copy the sorted elements back to the original array
for (int i = 0; i < n; i++) {
arr[i] = output[i];
}
}
// Radix Sort function
void radixSort(int arr[], int n) {
// Find the maximum number to determine the number of digits
int max = findMax(arr, n);
// Perform counting sort for every digit place
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSort(arr, n, exp);
}
}
// Function to print an array
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
// Main function
int main() {
int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
printArray(arr, n);
// Perform Radix Sort
radixSort(arr, n);
printf("Sorted array: ");
printArray(arr, n);
return 0;
}
#4 Radix Sort implement in C++
Code -
C++ Programming
#include <iostream>
#include <vector>
using namespace std;
// Function to find the maximum number to determine the number of digits
int findMax(vector<int>& arr) {
int max = arr[0];
for (int i = 1; i < arr.size(); i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
// Using counting sort to sort the elements based on significant places
void countingSort(vector<int>& arr, int exp) {
const int n = arr.size();
const int k = 10; // 0 to 9
vector<int> output(n, 0);
vector<int> count(k, 0);
// Count the occurrences
for (int i = 0; i < n; i++) {
count[(arr[i] / exp) % 10]++;
}
// Update count[i] to store the position of the next occurrence
for (int i = 1; i < k; i++) {
count[i] += count[i - 1];
}
// Build the output array
for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
// Copy the output array back to the original array
for (int i = 0; i < n; i++) {
arr[i] = output[i];
}
}
// Radix Sort function
void radixSort(vector<int>& arr) {
int max = findMax(arr);
// Perform counting sort for every digit, starting from the least significant digit
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSort(arr, exp);
}
}
// Function to print an array
void printArray(const vector<int>& arr) {
for (int i = 0; i < arr.size(); i++) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
vector<int> arr = {170, 45, 75, 90, 802, 24, 2, 66};
cout << "Original array: ";
printArray(arr);
radixSort(arr);
cout << "Sorted array: ";
printArray(arr);
return 0;
}
Demonstration
Radix Sort Data Structure and Algorithm