Radix Sort

Radix Sort works by processing digits in numbers of the given list of numeric elements.

Working

Radix Sort operates on the principle of processing digits in numbers from the least significant to the most significant. It categorizes elements based on each digit, creating a sorted sequence after processing all digits. The process repeats until the entire number is sorted.

The algorithm is non-comparative, making it advantageous in scenarios where the range of elements is known. Radix Sort can handle integers, strings, or any other data types that can be broken down into digits.

Code

// C++ Code

#include <iostream>
#include <vector>

class RadixSort {

public:
    static void sort(std::vector<int>& arr) {

        int max = getMax(arr);
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSort(arr, exp);
        }
    }

private:
    static int getMax(const std::vector<int>& arr) {
        int max = arr[0];

        for (int i = 1; i < arr.size(); i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }

        return max;
    }

    static void countingSort(std::vector<int>& arr, int exp) {

        const int n = arr.size();
        std::vector<int> output(n, 0);
        std::vector<int> count(10, 0);

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

        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

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

        for (int i = 0; i < n; i++) {
            arr[i] = output[i];
        }
    }
};

int main() {

    std::vector<int> arr = {170, 45, 75, 90, 802, 24, 2, 66};
    RadixSort::sort(arr);
    std::cout << "Sorted Array: ";

    for (int num : arr) {
        std::cout << num << " ";
    }
    return 0;
}

Output

Sorted Array: 2 24 45 66 75 90 170 802

Explanation

• The getMax function determines the maximum element in the array.
• countingSort is a helper function implementing the counting sort algorithm for a specific digit place.
• The radixSort function iteratively applies counting sort for each digit place.
• The main function initializes an array, sorts it using radix sort, and prints the sorted array.

Complexity

• Time Complexity: O(nk), where n is the number of elements and k is the number of digits in the maximum element.
• Space Complexity: O(n + k), where n is the number of elements and k is the range of input.

Radix Sort, with its unique approach to sorting based on digits, is a powerful algorithm. Its linear time complexity makes it efficient for scenarios where the range of elements is known. As we've explored in this article, understanding the principles and implementation of Radix Sort can broaden your perspective on sorting algorithms and equip you with a valuable tool in your programming toolkit.