Radix Sort Algorithm: C++, Python Examples

What is a Sorting Algorithm?

A sorting algorithm consists of a set of instructions that are used for organizing elements present in a list or an array in a specific order. These algorithms are important in increasing the efficiency of a coding solution. Sorting algorithms have many uses, like in searching algorithms, data structure algorithms, etc.

What is the Radix Sort Algorithm?

Radix Sort is a non-comparative sorting algorithm. It works by grouping the individual digits of the elements to be sorted. A stable sorting technique is then used to organize the elements based on their radix. It is a linear sorting algorithm.

The sorting process involves the following properties:

  • Finding the maximum element and acquiring the number of digits of that element. It gives us the number of iterations the sorting process will follow.
  • Group the individual digits of the elements at the same significant position in each iteration.
  • Grouping process will start from the least significant digit and end at the most significant digit.
  • Sorting the elements based on digits at that significant position.
  • Maintaining the relative order of elements that have the same key value. This property of the radix sort makes it a stable sort.

The final iteration will give us a completely sorted list.

How Radix Sort Works

List of integers to be sorted

Let’s try to sort the list of integers in the above figure in an ascending order using the Radix Sort algorithm.

Here are the steps to perform the Radix Sorting process:

Step 1) Identify the element with the maximum value in the list. In this case, it is 835.

Step 2) Calculate the number of digits of the maximum element. 835 has 3 digits exactly.

Step 3) Determine the number of iterations based on step 2. 835 has 3 digits, meaning the number of iterations will be 3.

Step 4) Determine the base of the elements. Since this is a decimal system, the base will be 10.

Step 5) Start the first iteration.

a) First iteration

Sorting by the last digit
Sorting by the last digit

In the first iteration, we consider the unit place value of each element.

Step 1) Mod the integer by 10 to get the unit place of the elements. For example, 623 mod 10 gives us the value 3, and 248 mod 10 gives us 8.

Step 2) Use counting sort or any other stable sort to organize the integers according to their least significant digit. As seen From the figure, 248 will fall on the 8th bucket. 623 will fall on the 3rd bucket and so on.

After the first iteration, the list now looks like this.

List after the first iteration
List after the first iteration

As you can see from the above-given figure, the list is not sorted yet and requires more iteration to be fully sorted.

b) Second iteration

Sorting based on digits at tens place
Sorting based on digits at tens place

In this iteration, we will consider the digit at the 10th place for the sorting process.

Step 1) Divide the integers by 10. 248 divided by 10 gives us 24.

Step 2) Mod the output of step 1 by 10. 24 mod 10 gives us 4.

Step 3) Follow step 2 from the previous iteration.

After the second iteration, the list now looks like this

List after the second iteration
List after the second iteration

You can see from the above-given figure that the list is still not sorted completely as it is not in ascending order yet.

c) Third iteration

Sorting based on the digits at hundreds of places
Sorting based on the digits at hundreds of places

For the final iteration, we want to get the most significant digit. In this case, it’s the 100th place for each of the integers in the list.

Step 1) Divide the integers by 100… 415 divided by 100 gives us 4.

Step 2) Mod the result from step 1 by 10. 4 mod 10 gives us 4 again.

Step 3) Follow step 3 from the previous iteration.

List after the third iteration
List after the third iteration

As we can see, the list is sorted now in ascending order. The final iteration has been completed, and the sorting process is now finished.

Pseudocode of Radix Sort

Here is the pseudo-code for the Radix Sort Algorithm

radixSortAlgo(arr as an array)
  Find the largest element in arr
  maximum=the element in arr that is the largest
  Find the number of digits in maximum
  k=the number of digits in maximum 
  Create buckets of size 0-9 k times
for j -> 0 to k
  Acquire the jth place of each element in arr. Here j=0 represents the least significant digit.
  Use a stable sorting algorithm like counting sort to sort the elements in arr according to the digits of the elements in the jthplace
   arr = sorted elements

C++ implementation of Radix Sort

#include <iostream>
using namespace std;
// Function to get the largest element in an array
int getMaximum(int arr[], int n) {
  int maximum = arr[0];
  for (int i = 1; i < n; i++) {
    if (maximum < arr[i]) maximum = arr[i];
  }
  return maximum;
}
// We are using counting sort to sort the elements digit by digit
void countingSortAlgo(int arr[], int size, int position) {
  const int limit = 10;
  int result[size];
  int count[limit] = {0};
  // Calculating the count of each integers
  for (int j = 0; j < size; j++) count[(arr[j] / position) % 10]++;
  // Calculating the cumulative count
  for (int j = 1; j < limit; j++) {
    count[j] += count[j - 1];
  }
  // Sort the integers
  for (int j = size - 1; j >= 0; j--) {
    result[count[(arr[j] / position) % 10] - 1] = arr[j];
    count[(arr[j] / position) % 10]--;
  }
  for (int i = 0; i < size; i++) arr[i] = result[i];
}
// The radixSort algorithm
void radixSortAlgo(int arr[], int size) {
  // Get the largest element in the array
  int maximum = getMaximum(arr, size);
  for (int position = 1; maximum / position > 0; position *= 10)
    countingSortAlgo(arr, size, position);
}
// Printing final result
void printResult(int arr[], int size) {
  for (int i = 0; i < size; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;
}
int main() {
  int arr[] = {162, 623, 835, 415, 248};
  int size = sizeof(arr) / sizeof(arr[0]);
  radixSortAlgo(arr, size);
  printResult(arr, size);
}

Output:

162 248 415 623 835

Python implementation of Radix Sort

#Radix Sort using python
def countingSortAlgo(arr, position):
    n = len(arr)
result = [0] * n
count = [0] * 10# Calculating the count of elements in the array arr
for j in range(0, n):
    element = arr[j] // position
count[element % 10] += 1# Calculating the cumulative count
for j in range(1, 10):
    count[j] += count[j - 1]# Sorting the elements
i = n - 1
while i >= 0:
    element = arr[i] // position
result[count[element % 10] - 1] = arr[i]
count[element % 10] -= 1
i -= 1
for j in range(0, n):
    arr[j] = result[j]
def radixSortAlgo(arr): #Acquiring the largest element in the array
maximum = max(arr)# Using counting sort to sort digit by digit
position = 1
while maximum // position>0:
countingSortAlgo(arr, position)
position *= 10
input = [162, 623, 835, 415, 248]
radixSortAlgo(input)
print(input)

Output:

[162,248,415,623,835]

Complexity analysis of Radix Sort

There are two types of complexity to consider, space complexity and time complexity.

  • Space complexity: O(n+b) where n is the size of the array and b is the base considered.
  • Time complexity: O(d*(n+b)) where d is the number of digits of the largest element in the array.

Space Complexity of Radix Sort

Two features to focus on for space complexity

  • Number of elements in the array, n.
  • The base for representing the elements, b.

Sometimes this base can be greater than the size of the array.

The overall complexity is thus O(n+b).

The following properties of the elements in the list can make radix sort space inefficient:

  • Elements with a large number of digits.
  • Base of the elements is large, like 64-bit numbers.

Time Complexity of Radix Sort

You can use the counting sort as a subroutine, as each iteration will take O(n+b) time. If d iterations exist, the total running time becomes O(d*(n+b)). Here, “O” means the complexity function.

Linearity of Radix Sort

Radix Sort is linear when

  • d is constant, where d is the number of digits of the largest element.
  • b is not larger to a great extent compared to n.

Comparisons of Radix Sort with other comparative algorithms.

As we’ve seen, the Radix sort’s complexity is based on a word or number size. It will have the same complexity for the average and best cases. And that is O(d*(n+b)). Also, it differs according to the sorting technique you use in the middle. For example, you can use counting sort or quick sort for the intermediate sorting algorithm inside the Radix sort.

Applications of Radix Sort

Important Applications of Radix Sort are:

  • Radix Sort can be used as a location finding algorithm where large ranges of values are used.
  • It is used in constructing a suffix array in the DC3 algorithm.
  • It is used In a sequential, random-access machine present in a typical computer where records are keyed.