Radix Sort Algorithm Code Implementations
Complete Radix Sort Algorithm code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.
Read Radix Sort Algorithm Guide ยท Launch Interactive Visualizer
C++ Implementation
// Radix Sort Implementation in C++
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
class RadixSort {
public:
static std::vector<int> radixSort(const std::vector<int>& arr) {
if (arr.size() <= 1) {
return arr;
}
std::vector<int> sortedArray = arr;
int maxNum = getMax(sortedArray);
int maxDigits = static_cast<int>(log10(abs(maxNum))) + 1;
// Perform counting sort for each digit
for (int digit = 0; digit < maxDigits; digit++) {
countingSortByDigit(sortedArray, digit);
}
return sortedArray;
}
private:
static void countingSortByDigit(std::vector<int>& arr, int digit) {
int n = arr.size();
std::vector<int> output(n);
std::vector<int> count(10, 0);
// Count occurrences of each digit
for (int i = 0; i < n; i++) {
int digitValue = (arr[i] / static_cast<int>(pow(10, digit))) % 10;
count[digitValue]++;
}
// Calculate cumulative count
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
// Build output array
for (int i = n - 1; i >= 0; i--) {
int digitValue = (arr[i] / static_cast<int>(pow(10, digit))) % 10;
output[count[digitValue] - 1] = arr[i];
count[digitValue]--;
}
// Copy output back to original array
for (int i = 0; i < n; i++) {
arr[i] = output[i];
}
}
static int getMax(const std::vector<int>& arr) {
return *std::max_element(arr.begin(), arr.end());
}
public:
// LSD (Least Significant Digit) Radix Sort
static std::vector<int> radixSortLSD(const std::vector<int>& arr) {
if (arr.size() <= 1) {
return arr;
}
std::vector<int> sortedArray = arr;
int maxNum = getMax(sortedArray);
int maxDigits = static_cast<int>(log10(abs(maxNum))) + 1;
// Use buckets for each digit (0-9)
for (int digit = 0; digit < maxDigits; digit++) {
std::vector<std::vector<int>> buckets(10);
// Distribute elements into buckets
for (int num : sortedArray) {
int digitValue = (num / static_cast<int>(pow(10, digit))) % 10;
buckets[digitValue].push_back(num);
}
// Collect elements from buckets
int index = 0;
for (int bucket = 0; bucket < 10; bucket++) {
for (int num : buckets[bucket]) {
sortedArray[index++] = num;
}
}
}
return sortedArray;
}
// MSD (Most Significant Digit) Radix Sort
static std::vector<int> radixSortMSD(const std::vector<int>& arr) {
if (arr.size() <= 1) {
return arr;
}
std::vector<int> sortedArray = arr;
int maxNum = getMax(sortedArray);
int maxDigits = static_cast<int>(log10(abs(maxNum))) + 1;
return radixSortMSDHelper(sortedArray, maxDigits - 1);
}
private:
static std::vector<int> radixSortMSDHelper(const std::vector<int>& arr, int digit) {
if (digit < 0 || arr.size() <= 1) {
return arr;
}
std::vector<std::vector<int>> buckets(10);
// Distribute elements into buckets
for (int num : arr) {
int digitValue = (num / static_cast<int>(pow(10, digit))) % 10;
buckets[digitValue].push_back(num);
}
// Recursively sort each bucket
std::vector<int> result;
for (int bucket = 0; bucket < 10; bucket++) {
if (!buckets[bucket].empty()) {
std::vector<int> sortedBucket = radixSortMSDHelper(buckets[bucket], digit - 1);
result.insert(result.end(), sortedBucket.begin(), sortedBucket.end());
}
}
return result;
}
};JAVA Implementation
// Radix Sort Implementation in Java
public class RadixSort {
public static int[] radixSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return arr.clone();
}
int[] sortedArray = arr.clone();
int maxNum = getMax(sortedArray);
int maxDigits = (int) Math.log10(Math.abs(maxNum)) + 1;
// Perform counting sort for each digit
for (int digit = 0; digit < maxDigits; digit++) {
countingSortByDigit(sortedArray, digit);
}
return sortedArray;
}
private static void countingSortByDigit(int[] arr, int digit) {
int n = arr.length;
int[] output = new int[n];
int[] count = new int[10];
// Count occurrences of each digit
for (int i = 0; i < n; i++) {
int digitValue = (arr[i] / (int) Math.pow(10, digit)) % 10;
count[digitValue]++;
}
// Calculate cumulative count
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
// Build output array
for (int i = n - 1; i >= 0; i--) {
int digitValue = (arr[i] / (int) Math.pow(10, digit)) % 10;
output[count[digitValue] - 1] = arr[i];
count[digitValue]--;
}
// Copy output back to original array
for (int i = 0; i < n; i++) {
arr[i] = output[i];
}
}
private static int getMax(int[] arr) {
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
// LSD (Least Significant Digit) Radix Sort
public static int[] radixSortLSD(int[] arr) {
if (arr == null || arr.length <= 1) {
return arr.clone();
}
int[] sortedArray = arr.clone();
int maxNum = getMax(sortedArray);
int maxDigits = (int) Math.log10(Math.abs(maxNum)) + 1;
// Use buckets for each digit (0-9)
for (int digit = 0; digit < maxDigits; digit++) {
int[][] buckets = new int[10][];
int[] bucketSizes = new int[10];
// Count elements for each bucket
for (int num : sortedArray) {
int digitValue = (num / (int) Math.pow(10, digit)) % 10;
bucketSizes[digitValue]++;
}
// Initialize buckets
for (int i = 0; i < 10; i++) {
buckets[i] = new int[bucketSizes[i]];
}
// Distribute elements into buckets
int[] bucketIndices = new int[10];
for (int num : sortedArray) {
int digitValue = (num / (int) Math.pow(10, digit)) % 10;
buckets[digitValue][bucketIndices[digitValue]++] = num;
}
// Collect elements from buckets
int index = 0;
for (int bucket = 0; bucket < 10; bucket++) {
for (int j = 0; j < bucketSizes[bucket]; j++) {
sortedArray[index++] = buckets[bucket][j];
}
}
}
return sortedArray;
}
// MSD (Most Significant Digit) Radix Sort
public static int[] radixSortMSD(int[] arr) {
if (arr == null || arr.length <= 1) {
return arr.clone();
}
int[] sortedArray = arr.clone();
int maxNum = getMax(sortedArray);
int maxDigits = (int) Math.log10(Math.abs(maxNum)) + 1;
return radixSortMSDHelper(sortedArray, maxDigits - 1);
}
private static int[] radixSortMSDHelper(int[] arr, int digit) {
if (digit < 0 || arr.length <= 1) {
return arr;
}
int[][] buckets = new int[10][];
int[] bucketSizes = new int[10];
// Count elements for each bucket
for (int num : arr) {
int digitValue = (num / (int) Math.pow(10, digit)) % 10;
bucketSizes[digitValue]++;
}
// Initialize buckets
for (int i = 0; i < 10; i++) {
buckets[i] = new int[bucketSizes[i]];
}
// Distribute elements into buckets
int[] bucketIndices = new int[10];
for (int num : arr) {
int digitValue = (num / (int) Math.pow(10, digit)) % 10;
buckets[digitValue][bucketIndices[digitValue]++] = num;
}
// Recursively sort each bucket
int[] result = new int[arr.length];
int resultIndex = 0;
for (int bucket = 0; bucket < 10; bucket++) {
if (bucketSizes[bucket] > 0) {
int[] sortedBucket = radixSortMSDHelper(buckets[bucket], digit - 1);
System.arraycopy(sortedBucket, 0, result, resultIndex, sortedBucket.length);
resultIndex += sortedBucket.length;
}
}
return result;
}
}JAVASCRIPT Implementation
// Radix Sort Implementation in JavaScript
function radixSort(arr) {
if (arr.length <= 1) {
return [...arr];
}
const sortedArray = [...arr];
const maxNum = Math.max(...sortedArray);
const maxDigits = Math.floor(Math.log10(Math.abs(maxNum))) + 1;
// Perform counting sort for each digit
for (let digit = 0; digit < maxDigits; digit++) {
countingSortByDigit(sortedArray, digit);
}
return sortedArray;
}
function countingSortByDigit(arr, digit) {
const n = arr.length;
const output = new Array(n);
const count = new Array(10).fill(0);
// Count occurrences of each digit
for (let i = 0; i < n; i++) {
const digitValue = Math.floor(arr[i] / Math.pow(10, digit)) % 10;
count[digitValue]++;
}
// Calculate cumulative count
for (let i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
// Build output array
for (let i = n - 1; i >= 0; i--) {
const digitValue = Math.floor(arr[i] / Math.pow(10, digit)) % 10;
output[count[digitValue] - 1] = arr[i];
count[digitValue]--;
}
// Copy output back to original array
for (let i = 0; i < n; i++) {
arr[i] = output[i];
}
}
// LSD (Least Significant Digit) Radix Sort
function radixSortLSD(arr) {
if (arr.length <= 1) {
return [...arr];
}
const sortedArray = [...arr];
const maxNum = Math.max(...sortedArray);
const maxDigits = Math.floor(Math.log10(Math.abs(maxNum))) + 1;
// Use buckets for each digit (0-9)
for (let digit = 0; digit < maxDigits; digit++) {
const buckets = Array.from({ length: 10 }, () => []);
// Distribute elements into buckets
for (let i = 0; i < sortedArray.length; i++) {
const digitValue = Math.floor(sortedArray[i] / Math.pow(10, digit)) % 10;
buckets[digitValue].push(sortedArray[i]);
}
// Collect elements from buckets
let index = 0;
for (let bucket = 0; bucket < 10; bucket++) {
for (let j = 0; j < buckets[bucket].length; j++) {
sortedArray[index++] = buckets[bucket][j];
}
}
}
return sortedArray;
}
// MSD (Most Significant Digit) Radix Sort
function radixSortMSD(arr) {
if (arr.length <= 1) {
return [...arr];
}
const sortedArray = [...arr];
const maxNum = Math.max(...sortedArray);
const maxDigits = Math.floor(Math.log10(Math.abs(maxNum))) + 1;
return radixSortMSDHelper(sortedArray, maxDigits - 1);
}
function radixSortMSDHelper(arr, digit) {
if (digit < 0 || arr.length <= 1) {
return arr;
}
const buckets = Array.from({ length: 10 }, () => []);
// Distribute elements into buckets
for (let i = 0; i < arr.length; i++) {
const digitValue = Math.floor(arr[i] / Math.pow(10, digit)) % 10;
buckets[digitValue].push(arr[i]);
}
// Recursively sort each bucket
const result = [];
for (let bucket = 0; bucket < 10; bucket++) {
if (buckets[bucket].length > 0) {
const sortedBucket = radixSortMSDHelper(buckets[bucket], digit - 1);
result.push(...sortedBucket);
}
}
return result;
}PYTHON Implementation
# Radix Sort Implementation in Python
def radix_sort(arr):
if len(arr) <= 1:
return arr.copy()
sorted_array = arr.copy()
max_num = max(sorted_array)
max_digits = len(str(abs(max_num)))
# Perform counting sort for each digit
for digit in range(max_digits):
counting_sort_by_digit(sorted_array, digit)
return sorted_array
def counting_sort_by_digit(arr, digit):
n = len(arr)
output = [0] * n
count = [0] * 10
# Count occurrences of each digit
for i in range(n):
digit_value = (arr[i] // (10 ** digit)) % 10
count[digit_value] += 1
# Calculate cumulative count
for i in range(1, 10):
count[i] += count[i - 1]
# Build output array
for i in range(n - 1, -1, -1):
digit_value = (arr[i] // (10 ** digit)) % 10
output[count[digit_value] - 1] = arr[i]
count[digit_value] -= 1
# Copy output back to original array
for i in range(n):
arr[i] = output[i]
# LSD (Least Significant Digit) Radix Sort
def radix_sort_lsd(arr):
if len(arr) <= 1:
return arr.copy()
sorted_array = arr.copy()
max_num = max(sorted_array)
max_digits = len(str(abs(max_num)))
# Use buckets for each digit (0-9)
for digit in range(max_digits):
buckets = [[] for _ in range(10)]
# Distribute elements into buckets
for num in sorted_array:
digit_value = (num // (10 ** digit)) % 10
buckets[digit_value].append(num)
# Collect elements from buckets
index = 0
for bucket in buckets:
for num in bucket:
sorted_array[index] = num
index += 1
return sorted_array
# MSD (Most Significant Digit) Radix Sort
def radix_sort_msd(arr):
if len(arr) <= 1:
return arr.copy()
sorted_array = arr.copy()
max_num = max(sorted_array)
max_digits = len(str(abs(max_num)))
return radix_sort_msd_helper(sorted_array, max_digits - 1)
def radix_sort_msd_helper(arr, digit):
if digit < 0 or len(arr) <= 1:
return arr
buckets = [[] for _ in range(10)]
# Distribute elements into buckets
for num in arr:
digit_value = (num // (10 ** digit)) % 10
buckets[digit_value].append(num)
# Recursively sort each bucket
result = []
for bucket in buckets:
if bucket:
sorted_bucket = radix_sort_msd_helper(bucket, digit - 1)
result.extend(sorted_bucket)
return result