What Is Radix Sort in Data Structure Using C?

What Is Radix Sort in Data Structure Using C?

The radix sort algorithm is a sorting technique that operates on integers by examining the individual digits of each number. It is an efficient sorting algorithm that can be used to sort large sets of data quickly. In this tutorial, we will explore the concept of radix sort and how it can be implemented using the C programming language.

Radix Sort Algorithm

The radix sort algorithm sorts numbers by considering each digit at different positions within the numbers. It starts by sorting the least significant digit and then continues to sort digits of increasing significance until all digits have been considered. This process is repeated until the entire set of numbers is sorted.

The key idea behind radix sort is to use stable sorting algorithms for each digit position. A stable sorting algorithm preserves the relative order of elements with equal keys. The most commonly used stable sorting algorithms for radix sort are counting sort and bucket sort.

Steps of Radix Sort:

1. Find the maximum element in the array to determine the number of digits.
2. Iterate through each digit position, starting from the least significant digit.
3. Use a stable sorting algorithm to sort the elements based on the current digit position.
4. Repeat step 3 until all digits have been considered.

Implementation in C

To implement radix sort in C, we need to define functions for counting sort and finding the maximum element in an array:

#include <stdio.h>
#include <stdlib.h>

// Function to find the maximum element in an array
int findMax(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 position
void countingSort(int arr[], int n, int exp) {
    int output[n]; // Output array
    int count[10] = {0}; // Counting array

    // 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 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--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }

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

// Function to perform radix sort
void radixSort(int arr[], int n) {
    int max = findMax(arr, n);

    // Perform counting sort for every digit position
    for (int exp = 1; max / exp > 0; exp *= 10) {
        countingSort(arr, n, exp);
    }
}

// Driver code
int main() {
    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
    int n = sizeof(arr) / sizeof(arr[0]);

    radixSort(arr, n);

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

    return 0;
}

In the above implementation, the findMax() function is used to find the maximum element in the array. The countingSort() function performs counting sort based on the current digit position. Finally, the radixSort() function uses these helper functions to sort the array using radix sort.

Conclusion

Radix sort is an efficient sorting algorithm that operates on integers by examining their individual digits. It can be implemented using stable sorting algorithms like counting sort or bucket sort.

By considering each digit position from least significant to most significant, radix sort sorts numbers in a step-by-step manner. This tutorial provided an in-depth overview of radix sort and demonstrated its implementation using the C programming language.

Note: It is important to note that radix sort is only suitable for sorting non-negative integer values.

I hope this tutorial has helped you understand what radix sort is and how it can be implemented using C. Feel free to experiment with different inputs and explore other sorting algorithms as well!