Home Data Structures and Algorithms with C++ Radix Sort in C++

Lesson 35 of 48

In Progress

← Previous Next→

Radix Sort in C++

Yasin Cakal

Radix sort is an efficient sorting algorithm that is used to sort large numbers of items into a specific order. This sorting algorithm works by arranging the data into a sequence of “buckets” which are organized according to their most significant digit. In this article, we will discuss the radix sort algorithm and its implementation in C++. We will also explore its time and space complexity, as well as provide coding exercises and solutions to further solidify your understanding of this sorting algorithm.

How Does the Radix Sort Algorithm Work?

Radix sort is a non-comparative sorting algorithm. It works by sorting the data into buckets based on their most significant digit, then progressing to the least significant digit. To accomplish this, the algorithm uses a counting sort as a subroutine to sort each bucket.

Let’s take a look at how radix sort works on an example. Suppose we have the following array of numbers to be sorted:

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

The first step is to determine the number of digits in the largest number in the array. In this case, the largest number is 802, which has three digits. We will use this number of digits to determine the number of passes that the algorithm needs to make.

The algorithm makes one pass for each digit in the largest number. In this case, we need to make three passes.

In the first pass, we will sort the array based on the one’s digit. We will divide the array into buckets of numbers that have the same one’s digit. For example, the numbers 2 and 24 will be placed in the same bucket since they both have a one’s digit of 2. The buckets will look like this:

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

In the second pass, we will sort the array based on the ten’s digit. We will divide the array into buckets of numbers that have the same ten’s digit. For example, the numbers 45 and 75 will be placed in the same bucket since they both have a ten’s digit of 4. The buckets will look like this:

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

In the third pass, we will sort the array based on the hundred’s digit. We will divide the array into buckets of numbers that have the same hundred’s digit. For example, the numbers 170 and 802 will be placed in the same bucket since they both have a hundred’s digit of 8. The buckets will look like this:

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

Finally, we will concatenate the buckets in the same order that they were created in. This will result in the following sorted array:

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

Implementation of Radix Sort in C++

Let’s take a look at how to implement the radix sort algorithm in C++. We will begin by creating a function that takes an array of integers as a parameter and sorts it using the radix sort algorithm.

// Function to sort an array 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. 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);
}

The first step is to find the maximum number in the array. We can do this by looping through the array and comparing each element to the maximum.

// 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;
}

Once we have the maximum number, we can use it to determine the number of digits in the largest number. This number of digits will be used to determine the number of passes that the algorithm needs to make.

Next, we will create a counting sort subroutine that will be used to sort each bucket. The counting sort subroutine takes the array, the size of the array, and the current exponent as parameters. The exponent is used to determine the current digit that the array is being sorted on.

// A function to do counting sort of arr[] according to
// the digit represented by exp.
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];
}

Time and Space Complexity of Radix Sort

The time complexity of the radix sort algorithm is O(d*(n+b)), where d is the number of digits in the largest number, n is the number of items in the array, and b is the base of the numbers being sorted (in this case, b = 10).

The space complexity of the radix sort algorithm is O(n+b), as it requires an additional array to store the sorted items.

Conclusion

Radix Sort is an efficient sorting algorithm used to sort an array of integers. It is a non-comparative sorting algorithm that operates by sorting the elements of the array from least significant digit to the most significant digit. It has a time complexity of O(n) and a space complexity of O(n). Radix Sort is a useful sorting algorithm for data structures and algorithms with C++.

Exercises

Write a program to sort an array of integers using the radix sort algorithm.

#include <iostream>
using namespace std;

// Function to sort an array 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. 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);
}

// 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)
{
    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];
}

// Function to print an array
void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

// Driver code
int main()
{
    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
    int n = sizeof(arr)/sizeof(arr[0]);
    radixSort(arr, n);
    printArray(arr, n);
    return 0;
}

// Output:
// 2 24 45 66 75 90 170 802

Write a program to sort an array of strings using the radix sort algorithm.

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

// Function to sort an array of strings using radix sort
void radixSort(string arr[], int n)
{
    // Find the maximum length of the strings
    int m = getMaxLength(arr, n);

    // Do counting sort for every character. Note that instead
    // of passing character number, exp is passed. exp is the
    // current character position
    for (int exp = m - 1; exp >= 0; exp--)
        countSort(arr, n, exp);
}

// Function to get maximum length of the strings
int getMaxLength(string arr[], int n)
{
    int max_length = 0;
    for (int i = 0; i < n; i++)
        max_length = max(max_length, (int)arr[i].length());
    return max_length;
}

// A function to do counting sort of arr[] according to
// the character represented by exp
void countSort(string arr[], int n, int exp)
{
    string output[n]; // output array
    int i, count[256] = {0};

    // Store count of occurrences in count[]
    for (i = 0; i < n; i++)
        count[arr[i][exp]]++;

    // Change count[i] so that count[i] now contains actual
    // position of this character in output[]
    for (i = 1; i < 256; i++)
        count[i] += count[i - 1];

    // Build the output array
    for (i = n - 1; i >= 0; i--)
    {
        output[count[arr[i][exp]] - 1] = arr[i];
        count[arr[i][exp]]--;
    }

    // Copy the output array to arr[], so that arr[] now
    // contains sorted strings according to current character
    for (i = 0; i < n; i++)
        arr[i] = output[i];
}

// Function to print an array
void printArray(string arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

// Driver code
int main()
{
    string arr[] = {"c++", "java", "python", "ruby"};
    int n = sizeof(arr)/sizeof(arr[0]);
    radixSort(arr, n);
    printArray(arr, n);
    return 0;
}

// Output:
// c++ java python ruby

Write a C++ program to sort an array of numbers with varying number of digits using 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 
// the digit represented by exp. 
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. 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 array 
void print(int arr[], int n) 
{ 
    for (int i = 0; i < n; i++) 
        cout << arr[i] << " "; 
} 
  
// Driver program to test above functions 
int main() 
{ 
    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    radixsort(arr, n); 
    print(arr, n); 
    return 0; 
}

Write a C++ program to sort an array of strings with varying lengths using Radix Sort.

#include <iostream> 
#include <string> 
using namespace std; 
  
// A utility function to get maximum value in arr[] 
int getMax(string arr[], int n) 
{ 
    int mx = arr[0].length(); 
    for (int i = 1; i < n; i++) 
        if (arr[i].length() > mx) 
            mx = arr[i].length(); 
    return mx; 
} 
  
// A function to do counting sort of arr[] according to 
// the digit represented by exp. 
void countSort(string arr[], int n, int exp) 
{ 
    string 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]-'0']++; 
  
    // 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]-'0'] - 1] = arr[i]; 
        count[arr[i][exp]-'0']--; 
    } 
  
    // 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(string 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 = m-1; exp >= 0; exp--) 
        countSort(arr, n, exp); 
} 
  
// A utility function to print an array 
void print(string arr[], int n) 
{ 
    for (int i = 0; i < n; i++) 
        cout << arr[i] << " "; 
} 
  
// Driver program to test above functions 
int main() 
{ 
    string arr[] = {"cat", "dog", "bird", "apple", "elephant"}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    radixsort(arr, n); 
    print(arr, n); 
    return 0; 
} 

// Output:
// apple bird cat dog elephant

What is the space complexity of Radix sort?