Radix Sort

Radix Sort

Radix Sort is a non-comparative sorting algorithm that sorts integers by grouping numbers by individual digits, from the least significant digit (rightmost) to the most significant digit (leftmost). Radix Sort can be implemented using counting sort or bucket sort as the stable sorting algorithm for each digit.

Here’s how Radix Sort works:

1. Grouping by Digits: Starting from the least significant digit (rightmost), group the numbers based on that digit.
2. Stable Sort: Use a stable sorting algorithm (such as Counting Sort or Bucket Sort) to sort the numbers based on the current digit. The order of elements within each group is preserved.
3. Repeat: Repeat the process for each subsequent digit, moving towards the most significant digit.
4. Combine: After sorting all the digits, the array will be sorted.

Radix Sort can be implemented using the Least Significant Digit (LSD) or Most Significant Digit (MSD) approach. LSD radix sort starts from the rightmost digit, while MSD radix sort starts from the leftmost digit.

Here’s a simple implementation of LSD Radix Sort in C using counting sort as the stable sorting algorithm:

#include <stdlib.h>

// Function to get the maximum value in arr[]
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;
}

// Using counting sort to sort the elements based on significant places
void countingSort(int arr[], int n, int exp) {
    int output[n];
    int count[10] = {0};

    for (int i = 0; i < n; i++)
        count[(arr[i] / exp) % 10]++;

    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];

    for (int i = n - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }

    for (int i = 0; i < n; i++)
        arr[i] = output[i];
}

// Radix Sort
void radixSort(int arr[], int n) {
    int max = getMax(arr, n);

    for (int exp = 1; max / exp > 0; exp *= 10)
        countingSort(arr, n, exp);
}

// Print an array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

// Driver program to test radix sort
int main() {
    int arr[] = {17, 45, 75, 90, 24, 2, 66};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: \n");
    printArray(arr, n);

    radixSort(arr, n);

    printf("\nSorted array: \n");
    printArray(arr, n);
    return 0;
}

Output:

Original array: 
17 45 75 90 24 2 66 

Sorted array: 
2 17 24 45 66 75 90 

Time Complexity

The time complexity of Radix Sort is O(d⋅(n+k)), where n is the number of elements in the array, k is the range of input values, and d is the number of digits in the maximum number.

Here’s why:

• Counting Sort on each digit: Radix Sort processes each digit of the numbers separately. For each digit, it uses a stable sorting algorithm (such as Counting Sort) to sort the numbers. This operation takes O(n+k) time.
• Number of digits: The number of iterations through the digits is determined by the maximum number of digits present in any number in the array. This maximum number of digits is determined by the base of the number system being used. For example, in the decimal number system, the base is 10, so the maximum number of digits in any number is the logarithm of the maximum number in the array to the base 10.
• Overall Complexity: Since Radix Sort processes each digit individually using a stable sorting algorithm, the time complexity becomes O(d⋅(n+k)), where d is the number of digits in the maximum number.