Lecture 355:- Radix Sort

Radix Sort is a non-comparative integer sorting algorithm that sorts elements by processing individual digits. It works by first sorting the elements based on their least significant digit, then their second least significant digit, and so on, until all the digits have been considered. Radix Sort can be applied to integers and strings.

Here's how the Radix Sort algorithm works for integers:

1. Find the maximum element (max) in the input array to determine the number of digits in the maximum element.
2. For each digit position (from the least significant to the most significant digit), perform the following steps: a. Create ten buckets (0 to 9) to temporarily store the elements based on the current digit. b. Traverse the input array and distribute each element into the corresponding bucket based on the current digit. c. Gather the elements back from the buckets in their order and store them in the input array.
3. After processing all the digits, the input array will be sorted.

Here's the C++ implementation of Radix Sort for integers:

cppCopy code

#include <iostream> #include <vector> using namespace std; // Function to find the maximum element in the array int findMax(vector<int>& arr) {    int maxElement = arr[0];    for (int i = 1; i < arr.size(); i++) {        if (arr[i] > maxElement)            maxElement = arr[i];    }    return maxElement; } // Counting Sort function for a specific digit position void countingSort(vector<int>& arr, int exp) {    int n = arr.size();    vector<int> output(n);    vector<int> count(10, 0);    // Count the occurrences of each digit in the input array    for (int i = 0; i < n; i++)        count[(arr[i] / exp) % 10]++;    // Modify the count array to store cumulative sums    for (int i = 1; i < 10; i++)        count[i] += count[i - 1];    // Place elements in the output array in sorted order 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 output array to the input array    for (int i = 0; i < n; i++)        arr[i] = output[i]; } // Radix Sort function void radixSort(vector<int>& arr) {    int maxElement = findMax(arr);    // Perform counting sort for each digit position    for (int exp = 1; maxElement / exp > 0; exp *= 10)        countingSort(arr, exp); } // Function to display the elements of the array void display(const vector<int>& arr) {    for (int val : arr)        cout << val << " ";    cout << endl; } int main() {    vector<int> arr = {170, 45, 75, 90, 802, 24, 2, 66};    cout << "Original Array: ";    display(arr);    radixSort(arr);    cout << "Sorted Array: ";    display(arr);    return 0; }

In this implementation, the radixSort function performs the Radix Sort algorithm to sort the input array. The countingSort function is a helper function that performs Counting Sort for a specific digit position.

When you run this code, it will display the original array and then the sorted array after applying the Radix Sort algorithm.