📚 Radix Sort

• Radix Sort is a non-comparison based integer sorting algorithm.

• It sorts numbers digit by digit, starting from the least significant digit (LSD) to the most significant digit (MSD).

• It uses a stable sub-sorting algorithm like Counting Sort at each digit position.

👉 Idea:

Sort numbers based on 1s place, then 10s place, then 100s place, and so on.

✅ Key Point: Radix sort is very fast when number of digits is small compared to number of elements.

---

🛠️ Algorithm for Radix Sort

1. Find the maximum number to know the number of digits.

2. Start from Least Significant Digit (LSD).

3. Use stable counting sort based on the current digit.

4. Repeat for every digit (unit place, ten place, hundred place, etc).

---

Example

Let's sort:
[170, 45, 75, 90, 802, 24, 2, 66]

🔢 Pass 1: Units Place

Buckets (0–9):

• 0 → 170, 90
• 1 → —
• 2 → 802, 2
• 3 → —
• 4 → 24
• 5 → 45, 75
• 6 → 66
• 7 → —
• 8 → —
• 9 → —

after Pass 1: 170, 90, 802, 2, 24, 45, 75, 66

---

🔢 Pass 2: Tens Place

(Based on order after Pass 1: 170, 90, 802, 2, 24, 45, 75, 66)

• 0 → 802, 2
• 1 → —
• 2 → 24
• 3 → —
• 4 → 45
• 5 → —
• 6 → 66
• 7 → 170, 75
• 8 → —
• 9 → 90

after Pass 2: 802, 2, 24, 45, 66, 170, 75, 90

---

🔢 Pass 3: Hundreds Place

(Based on order after Pass 2: 802, 2, 24, 45, 66, 170, 75, 90)

• 0 → 2, 24, 45, 66, 75, 90
• 1 → 170
• 2 → —
• 3 → —
• 4 → —
• 5 → —
• 6 → —
• 7 → —
• 8 → 802
• 9 → —

✅ Final Sorted Order:

2, 24, 45, 66, 75, 90, 170, 802  

Example ( University Question)

Perform radix sort to sort the numbers 34, 21, 3, 121, 342, 65 and 44

👉 Maximum number = 342 → 3 digits
So we perform 3 passes (units, tens, hundreds)

🔢 Pass 1: Sort by Units Place

Buckets (0–9):

• 1 → 21, 121
• 2 → 342
• 3 → 3
• 4 → 34, 44
• 5 → 65

New Order:

21, 121, 342, 3, 34, 44, 65

🔢 Pass 2: Sort by Tens Place

Buckets:

0 → 3
2 → 21, 121
3 → 34
4 → 342, 44
6 → 65
New Order:

3, 21, 121, 34, 342, 44, 65

🔢 Pass 3: Sort by Hundreds Place

Buckets:

• 0 → 3, 21, 34, 44, 65
• 1 → 121
• 3 → 342

Final Sorted Order:

3, 21, 34, 44, 65, 121, 342

📋  Algorithm

RADIX_SORT(arr, n)

    1. Find the maximum number (max) in arr.
    2. Set exp = 1.
    3. While (max / exp) > 0:
        a. Perform COUNTING_SORT(arr, n, exp)
        b. Set exp = exp * 10

COUNTING_SORT(arr, n, exp)
    1. Create output array of size n (to store sorted elements temporarily).
    2. Create count array of size 10 (for digits 0-9), initialize with 0.
    
    3. Count occurrences of (arr[i] / exp) % 10 for every element i.
       (This extracts the current digit and counts it.)

    4. Modify count[] so that each element at index i
       contains the position of this digit in output[].

    5. Build the output[] array by placing elements in correct position
       based on the digit at current exp.

    6. Copy output[] back to arr[].

📈 Complexity

Feature	Details
Time Complexity	O(d*(n + k)) where d = number of digits, n = number of elements, k = base                  (usually 10)
Space Complexity	O(n + k)
Stable Sorting	✅ Yes
Best for	Sorting integers, large number of elements with small digit size

📌 Important Points:

• Radix Sort does not compare elements.

• It is stable.

• Works best when range of numbers is not huge.

• For larger digits or variable-length strings, Radix Sort with MSD is used.

C Program - Radix Sort

#include <stdio.h>

void printArray(int arr[], int n) {

    for (int i=0; i<n; i++)

        printf("%d ", arr[i]);

    printf("\n");

}

void readArray(int arr[], int n) {

    for (int i=0; i<n; i++)

        scanf("%d", &arr[i]);

    

}

// Function to get maximum value in array

int getMax(int arr[], int n) {

    int max = arr[0];

    for (int i = 1; i < n; i++)

        if (arr[i] > max)

            max = arr[i];

    return max;

}

// Function to do counting sort according to the digit represented by exp

void countingSort(int arr[], int n, int exp) {

    int output[n]; // output array

    int count[10] = {0}; // count array for digits (0 to 9)

    // 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] contains actual position

    for (int i = 1; i < 10; i++)

        count[i] += count[i - 1];

    // Build the output array (traversing from end for stability)

    for (int i = n - 1; i >= 0; i--) {

        int digit = (arr[i] / exp) % 10;

        output[count[digit] - 1] = arr[i];

        count[digit]--;

    }

    // Copy the output array to arr[]

    for (int i = 0; i < n; i++)

        arr[i] = output[i];

        printArray(arr, n);

}

// Radix Sort function

void radixSort(int arr[], int n) {

    int max = getMax(arr, n); // Find the maximum number

    // Apply counting sort for every digit (exp = 1, 10, 100, ...)

    for (int exp = 1; max / exp > 0; exp *= 10)

        countingSort(arr, n, exp);

}

int main() {

    int arr[50] ;

    int n;

    

    printf("Enter the number of elements \n");

    scanf("%d",&n);

    printf("Enter the array elements\n");

    readArray(arr,n);

    

    printf("Original array: ");

    printArray(arr, n);

    radixSort(arr,n);

    printf("Sorted array: ");

    printArray(arr, n);

    return 0;

}

Output

Enter the number of elements 

8

Enter the array elements

170 45 75 90 802 24 2  66

Original array: 170 45 75 90 802 24 2 66 

170 90 802 2 24 45 75 66 

802 2 24 45 66 170 75 90 

2 24 45 66 75 90 170 802 

Sorted array: 2 24 45 66 75 90 170 802