AntInLoop

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