Implement Radix Sort Using C++

If you’re in a computer science background, widening your technical horizons is the best thing you should do. However, your programming skills matter the most. And one must continuously keep sharpening these skills, to become a better programmer in the future. Though there are multiple things to focus on, one specific area you must focus on is the world of data structures. Data structures in general are particular approaches to solve problems so that computer resources get used minimum. In general, there are multiple data structures you can learn and implement as well. However, we’ve covered some basic data structures before, so, now we’ll move towards some advanced data structures. Hence, today we’re going to learn how to Implement Radix Sort using C++.

 

What is Radix Sort?

 

• Unlike simpler data structures, Radix Sort uses a different sorting approach to arrange elements in sequential order.

 

• Here, elements (be it Integers or Strings) are sorted based on the position of digits i.e, from least significant to most significant.

 

• No of iterations in this sorting method may vary significantly. As iterations are directly proportional to the no of digits present in the largest element in a list/array.

 

Also Read: Implement Bubble Sort using C++

 

What’s The Approach?

 

• To make this program look cleaner and easier, we’ll divide it into three major sections.

 

• In the first part, we’ll find the largest number in an array using getMax().

 

• As for the second part, we’ll pass the exponential exp value to the counting sort function.

 

• At the final stage, we’ll apply counting sort to sort the array in ascending order w.r.t the exponential value being passed.

 

• In Counting Sort, we are going to sort array elements based on single digits only. Starting from one’s place and incrementing the exponential by 10 for each iteration. This condition is going to be executed till m/exp > 0   remains true (m holds the value of the largest integer in an array).

 

C++ Program To Implement Radix Sort

 

Input:

170, 45, 75, 90, 802, 24, 2, 66

 

Output:

2 24 45 66 75 90 170 802

// C++ implementation of Radix Sort
#include <iostream>
using namespace std;

// 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
void countSort(int arr[], int n, int exp)
{
    int output[n]; // output array
    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 Sort
void 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.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 array
void print(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}

// Driver Code
int main()
{
    int arr[] = { 170, 45, 75, 90, 802, 24, 2, 66 };
    int n = sizeof(arr) / sizeof(arr[0]);
    
    // Function Call
    radixsort(arr, n);
    print(arr, n);
    return 0;
}