Radix Sort is a linear sorting algorithm that sorts elements by processing them digit by digit. It is an efficient sorting algorithm for integers or strings with fixed-size keys.
Rather than comparing elements directly, Radix Sort distributes the elements into buckets based on each digit’s value. By repeatedly sorting the elements by their significant digits, from the least significant to the most significant, Radix Sort achieves the final sorted order.
Radix Sort Algorithm
The key idea behind Radix Sort is to exploit the concept of place value. It assumes that sorting numbers digit by digit will eventually result in a fully sorted list. Radix Sort can be performed using different variations, such as Least Significant Digit (LSD) Radix Sort or Most Significant Digit (MSD) Radix Sort.
Radix Sort of an array
Below is the implementation of the Radix Sort in C.
C
// C Program to implement Radix Sort#include <stdio.h>// A utility function to get maximum value in arr[]int getMax(int arr[], int n){ int mx = arr[0]; for (int i = 1; i < n; i++) if (arr[i] > mx) mx = arr[i]; return mx;}// A function to do counting sort of arr[] according to// the digit represented by exp.void countSort(int arr[], int n, int exp){ // output array int output[n]; int i, count[10] = { 0 }; // 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 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 Sortvoid radixsort(int arr[], int n){ // Find the maximum number to know number of digits int m = getMax(arr, n); // 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);}// A utility function to print an arrayvoid print(int arr[], int n){ for (int i = 0; i < n; i++) printf("%d ", arr[i]);}// Driver program to test above functionsint main(){ int arr[] = { 170, 45, 75, 90, 802, 24, 2, 66 }; int n = sizeof(arr) / sizeof(arr[0]); // Radix sort function radixsort(arr, n); print(arr, n); return 0;} |
2 24 45 66 75 90 170 802
Time Complexity: O(n*d), Here d =10
Auxiliary Space: O(n)
Please refer complete article on Radix Sort for more details!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
