Scroll Progress Bar

Radix sort

Radix sort is a non-comparison-based sorting algorithm that works by sorting elements based on their individual digits or characters. It is typically used to sort integers or strings. Here's a C++ implementation of radix sort for integers with comments and Sample Output:

Program:

    #include <iostream>
    #include <vector>
    
    // Function to find the maximum element in the array
    int getMax(std::vector& arr) {
        int max = arr[0];
        for (int num : arr) {
            if (num > max) {
                max = num;
            }
        }
        return max;
    }
    
    // Function to perform counting sort based on a particular digit (exp)
    void countingSort(std::vector& arr, int exp) {
        int n = arr.size();
        std::vector output(n, 0);
        std::vector count(10, 0);
    
        // Count occurrences of each digit at the current place value
        for (int i = 0; i < n; i++) {
            count[(arr[i] / exp) % 10]++;
        }
    
        // Update count[i] to contain the position of digit i in the output
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }
    
        // Build the output array by placing elements in their correct sorted positions
        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 back to the original array
        for (int i = 0; i < n; i++) {
            arr[i] = output[i];
        }
    }
    
    // Radix sort function
    void radixSort(std::vector& arr) {
        int max = getMax(arr);
    
        // Perform counting sort for every digit place value
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSort(arr, exp);
        }
    }
    
    int main() {
        std::vector arr = {170, 45, 75, 90, 802, 24, 2, 66};
    
        std::cout << "Original array: ";
        for (int num : arr) {
            std::cout << num << " ";
        }
    
        // Perform radix sort
        radixSort(arr);
    
        std::cout << "\nSorted array: ";
        for (int num : arr) {
            std::cout << num << " ";
        }
    
        return 0;
    }
In this code:

getMax is a function that finds the maximum element in the input vector to determine the number of digits in the largest number.

countingSort is a function that performs counting sort based on a particular digit (specified by exp). It counts occurrences of each digit at the current place value and builds the sorted output.

radixSort is the main sorting function that uses counting sort for each digit place value, starting from the least signifiit cant digit (units place) to the most signifiit cant digit.

Sample Output:

    Original array: 170 45 75 90 802 24 2 66 
    Sorted array: 2 24 45 66 75 90 170 802
As shown in the sample output, the input vector is successfully sorted using radix sort.

question

answer

question2

answer2