C Program That Implement Radix Sort To Sort A Given List Of Integers In Ascending Order

Radix sort is a non-comparative integer sorting algorithm that sorts data with integer keys by grouping keys by individual digits which share the same significant position and value. In this article, you will learn how to implement Radix Sort in C to efficiently sort a given list of non-negative integers in ascending order.

Problem Statement

Sorting a list of integers is a fundamental task in computer science, crucial for data organization, search efficiency, and algorithmic performance. While comparative sorts like Quick Sort or Merge Sort have O(N log N) time complexity, they might not be the most efficient for large lists of integers with a limited range or known digit characteristics. The challenge lies in finding an algorithm that can sort numbers based on their digits, potentially outperforming comparison-based sorts under specific conditions.

Example

Consider an unsorted list of integers: [170, 45, 75, 90, 802, 24, 2, 66]. After applying Radix Sort, the list will be sorted in ascending order as: [2, 24, 45, 66, 75, 90, 170, 802].

Background & Knowledge Prerequisites

To understand and implement Radix Sort effectively, familiarity with the following concepts is beneficial:

• C Programming Basics: Variables, arrays, loops (for, while), functions, pointers.
• Array Manipulation: Accessing elements, iterating through arrays, dynamic memory allocation (though not strictly required for a fixed-size array example).
• Counting Sort: Radix Sort internally uses Counting Sort as a stable sorting algorithm for each digit. Understanding how Counting Sort works (for a given range) is key.

Use Cases or Case Studies

Radix Sort is particularly advantageous in scenarios involving large datasets of integers. Here are a few practical applications:

• Data Processing: Sorting large volumes of numerical data, such as sensor readings, financial transactions, or database indices, where the keys are integers within a known range.
• Packet Routing: In network routers, sorting IP addresses or packet IDs can be optimized using Radix Sort due to the fixed-length integer structure of these identifiers.
• Compiler Optimization: Sorting symbols or identifiers in symbol tables can sometimes leverage Radix Sort for speed if they can be represented as integers.
• Lexicographical Sorting: When sorting strings of fixed or similar lengths, they can often be treated as numbers (e.g., using ASCII values), making Radix Sort applicable for efficient lexicographical ordering.
• Graphics and Image Processing: Sorting pixel data based on color components (e.g., RGB values) in certain image processing algorithms.

Solution Approaches

Radix Sort works by sorting numbers digit by digit, from the least significant digit (LSD) to the most significant digit (MSD) or vice versa. The most common approach uses LSD Radix Sort with Counting Sort as a stable sub-routine.

Approach 1: LSD Radix Sort using Counting Sort

This approach sorts the input array multiple times based on individual digits. It uses Counting Sort to sort elements by their current significant digit, ensuring stability (elements with the same digit value maintain their relative order).

One-line summary:

The algorithm iteratively sorts the array based on each digit's place value (units, tens, hundreds, etc.) using a stable sorting algorithm like Counting Sort.

Code Example:

// Radix Sort Implementation
#include <stdio.h>
#include <stdlib.h> // For malloc, free, abs
#include <limits.h> // For INT_MIN

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

// A function to do counting sort of arr[] according to
// the digit represented by exp.
void countSort(int arr[], int n, int exp) {
    int output[n]; // output array
    int i, count[10] = {0}; // Count array for digits 0-9

    // Store count of occurrences in count[]
    for (i = 0; i < n; i++) {
        count[(arr[i] / exp) % 10]++;
    }

    // Change count[i] so that count[i] now contains actual
    // position of this digit in output[]
    for (i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    // Build the output array
    // Iterate from right to left to ensure stability
    for (i = n - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }

    // Copy the output array to arr[], so that arr[] now
    // contains sorted numbers according to current digit
    for (i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

// The main function to that sorts arr[] of size n using Radix Sort
void radixSort(int arr[], int n) {
    // Step 1: Find the maximum number to know number of digits
    int m = getMax(arr, n);

    // Step 2: Do counting sort for every digit. Note that instead
    // of passing digit number, exp is passed. exp is 10^i where i is current
    // digit number
    for (int exp = 1; m / exp > 0; exp *= 10) {
        countSort(arr, n, exp);
    }
}

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

int main() {
    // Step 1: Define an array of integers
    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
    int n = sizeof(arr) / sizeof(arr[0]);

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

    // Step 2: Apply Radix Sort
    radixSort(arr, n);

    printf("Sorted array: ");
    printArray(arr, n);

    return 0;
}

Run

Sample Output:

Original array: 170 45 75 90 802 24 2 66 
Sorted array: 2 24 45 66 75 90 170 802

Stepwise Explanation:

1. getMax(int arr[], int n):

• This helper function iterates through the input array arr to find the largest element.
• The maximum element is needed to determine the number of digits in the largest number, which dictates how many passes Radix Sort needs (one pass for each digit position).

1. countSort(int arr[], int n, int exp):

• This is a modified Counting Sort function that sorts elements based on a specific digit determined by exp (e.g., exp=1 for units digit, exp=10 for tens digit, exp=100 for hundreds digit, and so on).
• Initialization: It creates an output array to store the sorted elements and a count array of size 10 (for digits 0-9), initialized to all zeros.
• Counting Occurrences: It iterates through the input array arr. For each number arr[i], it extracts the digit at the position indicated by exp using (arr[i] / exp) % 10 and increments the corresponding count in the count array.
• Cumulative Count: It modifies the count array such that count[i] now stores the actual position of the digit i in the output array.
• Building Output: It iterates through the input arr from right to left (n-1 to 0). This ensures stability: if two numbers have the same digit at the current exp position, their relative order from the previous exp pass is preserved. It places arr[i] into its correct sorted position in output and decrements the corresponding count.
• Copying Back: Finally, it copies the sorted elements from output back into the original arr, effectively sorting the array by the current digit.

1. radixSort(int arr[], int n):

• This is the main Radix Sort function.
• Find Maximum: It first calls getMax to find the largest number m in the array.
• Iterate by Digit: It then enters a for loop that iterates with exp (exponent) values of 1, 10, 100, and so on. This loop continues as long as m / exp is greater than 0, meaning there are still digits to process in the largest number.
• Apply Counting Sort: In each iteration, it calls countSort(arr, n, exp) to sort the array based on the digit at the exp place value. This process repeats until all digits, from least significant to most significant, have been used for sorting.

Conclusion

Radix Sort offers an efficient, non-comparative approach to sorting integers, particularly when dealing with large datasets or numbers within a specific range. By leveraging Counting Sort as a stable sub-routine, it sorts numbers digit by digit, from the least significant to the most significant, resulting in a fully sorted array. Its linear time complexity in terms of digits and array size makes it a powerful tool for specific sorting challenges.

Summary

• Radix Sort is a non-comparative integer sorting algorithm.
• It sorts numbers by processing individual digits, typically from least significant to most significant (LSD).
• The implementation often relies on a stable sorting algorithm like Counting Sort for each digit pass.
• Time complexity is O(d \* (n + k)), where 'd' is the number of digits, 'n' is the number of elements, and 'k' is the base of the numbers (usually 10 for decimal).
• It is efficient for large datasets of integers, especially when 'd' and 'k' are small relative to 'n log n'.
• Requires helper functions to find the maximum element and perform digit-wise Counting Sort.