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 

Code Explanation

1. getMax Function

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;
}

• Purpose: Finds the maximum value in the array.
• How it works:
  • Initializes max with the first element of the array.
  • Iterates through the array and updates max if a larger element is found.
  • Returns the maximum value.

2. countingSort Function

void countingSort(int arr[], int n, int exp) {
    int output[n]; // Temporary array to store sorted elements
    int count[10] = {0}; // Count array for digits 0-9
 
    // Count occurrences of each digit at the current significant place
    for (int i = 0; i < n; i++)
        count[(arr[i] / exp) % 10]++;
 
    // Modify count array to contain cumulative sum
    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];
 
    // Reconstruct the sorted array based on the current digit
    for (int i = n - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }
 
    // Copy the sorted elements back to the original array
    for (int i = 0; i < n; i++)
        arr[i] = output[i];
}

• Purpose: Sorts the array based on a specific digit (significant place) using Counting Sort.
• How it works:
  1. Count occurrences:
     • Counts the occurrences of each digit (0-9) at the current significant place (exp).
  2. Cumulative sum:
     • Modifies the count array to store the cumulative sum of counts.
  3. Reconstruct the sorted array:
     • Places each element in its correct position in the output array based on the current digit.
     • Decrements the count for each digit after placing the element.
  4. Copy back to the original array:
     • Copies the sorted elements from output back to the original array (arr).

3. radixSort Function

void radixSort(int arr[], int n) {
    int max = getMax(arr, n); // Find the maximum value in the array
 
    // Perform counting sort for each significant place (1s, 10s, 100s, etc.)
    for (int exp = 1; max / exp > 0; exp *= 10)
        countingSort(arr, n, exp);
}

• Purpose: Sorts the array using Radix Sort.
• How it works:
  1. Finds the maximum value in the array using the getMax function.
  2. Iterates through each significant place (1s, 10s, 100s, etc.) and calls countingSort to sort the array based on the current digit.

4. printArray Function

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]); // Print each element
    printf("\n"); // Move to the next line after printing
}

• Purpose: Prints the elements of the array.
• How it works:
  • Iterates through the array and prints each element followed by a space.
  • After printing all elements, it adds a newline (\n) for better readability.

5. main Function

int main() {
    int arr[] = {17, 45, 75, 90, 24, 2, 66}; // Unsorted array
    int n = sizeof(arr) / sizeof(arr[0]); // Calculate array size
 
    printf("Original array: \n");
    printArray(arr, n); // Print original array
 
    radixSort(arr, n); // Sort the array
 
    printf("\nSorted array: \n");
    printArray(arr, n); // Print sorted array
    return 0;
}

• Purpose: Drives the program.
• How it works:
  1. Declares and initializes an array arr with unsorted integers.
  2. Calculates the size of the array (n) using sizeof(arr) / sizeof(arr[0]).
  3. Prints the original array using the printArray function.
  4. Calls the radixSort function to sort the array.
  5. Prints the sorted array using the printArray function.

Key Points

1. Radix Sort:
   • Time Complexity: O(d * (n + k)), where d is the number of digits in the maximum number, n is the number of elements, and k is the range of digits (0-9).
   • Space Complexity: O(n + k).
   • It is a non-comparison-based sorting algorithm, making it efficient for sorting integers with a fixed number of digits.
2. How Radix Sort Works:
   • Sorts numbers digit by digit, starting from the least significant digit (1s place) to the most significant digit.
   • Uses Counting Sort as a subroutine to sort the numbers based on each digit.
3. Limitations:
   • Works only for non-negative integers.
   • Requires additional space for the output and count arrays.