📚 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]

Step 1: Sort according to 1s place

• 170 → 0

• 45 → 5

• 75 → 5

• 90 → 0

• 802 → 2

• 24 → 4

• 2 → 2

• 66 → 6

Order after 1s place sort:
[170, 90, 802, 2, 24, 45, 75, 66]

---

Step 2: Sort according to 10s place

• 170 → 7

• 90 → 9

• 802 → 0

• 2 → 0

• 24 → 2

• 45 → 4

• 75 → 7

• 66 → 6

Order after 10s place sort:
[802, 2, 24, 45, 66, 170, 75, 90]

---

Step 3: Sort according to 100s place

• 802 → 8

• 2 → 0

• 24 → 0

• 45 → 0

• 66 → 0

• 170 → 1

• 75 → 0

• 90 → 0

Order after 100s place sort:
[2, 24, 45, 66, 75, 90, 170, 802]

✅ Now the array is sorted!

📋  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>

// 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];

}

// 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);

}

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]);

    

}

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
6
Enter the array elements
170 45 75 90 802 24
Original array: 170 45 75 90 802 24
Sorted array: 24 45 75 90 170 802