Radix Sort

Introduction

Radix Sort is a non-comparative sorting algorithm that sorts elements by processing them digit by digit. This method sorts numbers by looking at one digit at a time. Instead of comparing the whole numbers, it sorts them based on their digits, starting from the zero place (least significant digit) then moving to the ten place (next digit to the left), and so on.

Why is it called Radix Sort?

Radix refers to the base of a number system. For example, in decimal numbers, the radix (or base) is 10 because it uses digits from 0 to 9. Radix Sort takes advantage of this by sorting based on these digits.

How Radix Sort Works?

Find the largest number in the array.

Finding the largest number ensures that we know how many digits (or places) we need to sort. This step determines the number of iterations (or passes) required to process all digits of every number.

Start with the zero place.

Sort the numbers based on this digit using a stable sorting method like Count Sort.
Move to the next place (ten place) and sort again.
Repeat this process for each place (hundred place, thousand place, etc.) until all digits are sorted.

The array will be fully sorted after the last place is processed.

Implementation of Radix Sort

//radixsort.cpp
#include <iostream>
#include <vector>
using namespace std;
void countSort(vector<int> &v, int pos)
{
    int n = v.size();
    vector<int> freq(10, 0);
    for (int i = 0; i < n; i++)
    {
        freq[(v[i] / pos) % 10]++;
    }
    for (int i = 1; i < 10; i++)
    {
        freq[i] += freq[i - 1];
    }
    vector<int> ans(n);
    for (int i = n - 1; i >= 0; i--)
    {
        ans[--freq[(v[i] / pos) % 10]] = v[i];
    }
    for (int i = 0; i < n; i++)
    {
        v[i] = ans[i];
    }
}
void radixSort(vector<int> &v)
{
    int max_ele;
    for (auto x : v)
    {
        max_ele = max(max_ele, x);
    }
    for (int pos = 1; max_ele / pos > 0; pos *= 10)
    {
        countSort(v, pos);
    }
}
int main()
{
    vector<int> v{0,500,3,77,12,56,777};
    radixSort(v);
    for (int ele : v)
    {
        cout << ele << " ";
    }
}

# radix_sort.py
def counting_sort(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10
    
    # Count occurrences of each digit
    for i in range(n):
        index = arr[i] // exp % 10
        count[index] += 1
    
    # Change count[i] so that it contains the position of this digit
    for i in range(1, 10):
        count[i] += count[i - 1]
    
    # Build the output array
    i = n - 1
    while i >= 0:
        index = arr[i] // exp % 10
        output[count[index] - 1] = arr[i]
        count[index] -= 1
        i -= 1
    
    # Copy the output array to arr
    for i in range(n):
        arr[i] = output[i]

def radix_sort(arr):
    # Find the maximum number to know number of digits
    max_num = max(arr)
    
    # Do counting sort for every digit
    exp = 1
    while max_num // exp > 0:
        counting_sort(arr, exp)
        exp *= 10

# Example usage
arr = [0, 500, 3, 77, 12, 56, 777]
radix_sort(arr)
print(arr)

// radixSort.js
function countingSort(arr, exp) {
const n = arr.length;
const output = new Array(n).fill(0);
const count = new Array(10).fill(0);

// Count occurrences of each digit
for (let i = 0; i < n; i++) {
    const index = Math.floor(arr[i] / exp) % 10;
    count[index]++;
}

// Change count[i] so that it contains the position of this digit
for (let i = 1; i < 10; i++) {
    count[i] += count[i - 1];
}

// Build the output array
for (let i = n - 1; i >= 0; i--) {
    const index = Math.floor(arr[i] / exp) % 10;
    output[count[index] - 1] = arr[i];
    count[index]--;
}

// Copy the output array to arr
for (let i = 0; i < n; i++) {
    arr[i] = output[i];
}
}

function radixSort(arr) {
// Find the maximum number to know number of digits
const maxNum = Math.max(...arr);

// Do counting sort for every digit
for (let exp = 1; Math.floor(maxNum / exp) > 0; exp *= 10) {
    countingSort(arr, exp);
}

return arr;
}

// Example usage
const arr = [0, 500, 3, 77, 12, 56, 777];
radixSort(arr);
console.log(arr);

Time Complexity

Finding the Maximum Element: O(n)

To determine the number of digits d in the largest number.

Counting Sort for Each Digit: O(n + k)

Counting Sort runs once for each digit, where k is the range of digits, typically k = 10 for decimal numbers.

Number of Digits (d) in the Largest Number:

The process is repeated d times.

Time Complexity:O(d⋅(n+k))≈ O(n⋅d) since k = 10 is constant.

Space Complexity

For Auxiliary Array Space in Count Sort:O(n+k)

Space Complexity:O(n+k)