C Program to Implement Radix Sort

Introduction

Radix Sort is a non-comparative sorting algorithm that sorts numbers by processing individual digits. It sorts the numbers by their least significant digit (LSD) first, moving to the most significant digit (MSD). The process is repeated for each digit position, using a stable sorting algorithm like counting sort or bucket sort to maintain the relative order of numbers with the same digit in each position. Radix Sort works efficiently for sorting numbers or strings with a fixed size and is particularly useful for large datasets where each item has multiple digits.

Example:

• Input: Unsorted array [170, 45, 75, 90, 802, 24, 2, 66]
• Output: Sorted array [2, 24, 45, 66, 75, 90, 170, 802]

Problem Statement

Create a C program that:

• Implements the Radix Sort algorithm to sort an array of non-negative integers.
• Takes an unsorted array as input and outputs the sorted array.

Solution Steps

1. Include the Standard Libraries: Use #include <stdio.h> for standard input-output functions.
2. Implement the Counting Sort Function: This function will be used to sort elements based on individual digits.
3. Implement the Radix Sort Function: This function will apply counting sort for each digit starting from the least significant digit.
4. Create a Main Function: Allow the user to input the array, apply radix sort, and display the sorted array.

C Program to Implement Radix Sort

#include <stdio.h>

// Function to get the maximum value in the 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 perform counting sort based on the digit represented by exp
void countingSort(int arr[], int n, int exp) {
    int output[n];  // Output array
    int count[10] = {0};  // Initialize count array with zeros

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

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

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

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

// Function to implement Radix Sort
void radixSort(int arr[], int n) {
    // Find the maximum number to know the number of digits
    int max = getMax(arr, n);

    // Apply counting sort to sort elements based on each digit from least significant to most significant
    for (int exp = 1; max / exp > 0; exp *= 10) {
        countingSort(arr, n, exp);
    }
}

int main() {
    int n;

    // Input the size of the array
    printf("Enter the number of elements in the array: ");
    scanf("%d", &n);

    int arr[n];

    // Input the elements of the array
    printf("Enter %d elements:\n", n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    // Apply Radix Sort
    radixSort(arr, n);

    // Output the sorted array
    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;  // Return 0 to indicate successful execution
}

Explanation

Function to Get the Maximum Value in the Array

• The getMax function scans the entire array to find the maximum value, which is used to determine the number of digits in the largest number. This is important for knowing how many passes (iterations) of counting sort need to be performed.

Function to Perform Counting Sort

• The countingSort function sorts the array based on a specific digit, represented by the exp (exponent). It uses a counting array (count[]) to store the frequency of each digit and then arranges the elements in the output array accordingly.
• The process is stable, meaning that numbers with the same digit in the current position maintain their relative order.

Function to Implement Radix Sort

• The radixSort function iterates over each digit, starting from the least significant digit, and calls countingSort to sort the array based on that digit.
• This process is repeated until all digits have been processed.

Main Function

• The main function allows the user to input the size of the array and the elements.
• It then applies Radix Sort to the array and displays the sorted array.

Output Example

Example Output:

Enter the number of elements in the array: 8
Enter 8 elements:
170 45 75 90 802 24 2 66
Sorted array: 2 24 45 66 75 90 170 802

Example Output (Single Digit Numbers):

Enter the number of elements in the array: 5
Enter 5 elements:
5 3 8 6 2
Sorted array: 2 3 5 6 8

Conclusion

This C program demonstrates how to implement Radix Sort, an efficient and stable sorting algorithm for integers. Radix Sort is particularly effective for sorting large datasets of fixed-width integers or strings, and it can outperform comparison-based sorting algorithms like Quick Sort in specific scenarios. The program provides a clear example of how Radix Sort can be implemented using counting sort as a subroutine in C programming.