Radix Sort Algorithm – Basics to Implementation in C/C++

Radix Sort Featured Image

Radix Sort Algorithm is a unique sorting algorithm that works on the basic principle of numbers being an ensemble of digits. Radix Sort works only on integer values since integers have only a single mathematical component, digits.

In this sorting algorithm, the numbers are initially arranged according to their least significant digit, moving onto their most significant digit, while maintaining the previous order.


How Does the Radix Sort Algorithm Work?

Let us quickly jump to the details of the algorithm, with an example running side by side.

Radix Sort Input Array
Input Array

Step 1: Finding the maximum element

As we previously mentioned, the algorithm arranges numbers using the least significant digit to the most significant digit, therefore we need to know the range of these iterations. For this purpose, we need to find the maximum element.

Radix Sort Max Element
Maximum element in the array

After finding the maximum number, we need to count its digits.


Step 2: Count the number of digits of the maximum number

We need to know the number of times we have to arrange the array, therefore there is a necessity to count the number of digits.

Radix Sort No Of Digits
Number of digits of maximum element

As we can see, the maximum element has three digits, therefore the arrangement will be done thrice.


Step 3: Arrange the numbers on the basis of the least significant digit

The initial arrangement of sorting requires us to sort the elements on the basis of their least significant digit.

Radix Sort Lsd Edited
Arranging numbers using units place digit

The key point to note here is that, numbers having different units place, but identical digits in other positions are mutually arranged in the right way.

For instance, the number 36 at index 3, and the number 32 at index 7, have a different digit in the units place, but other digits are identical. Initially, 32 is after 36 in the array, but after arranging the numbers according to units place, 32 comes before 36.


Step 4: Arrange the numbers according to the next significant digit

Keeping the current arrangement intact, we will try to arrange the numbers on the basis of tens place.

For this purpose, we will need a stable sort while implementation. Stable sorting algorithms are those, which preserves the initial arrangement of equal numbers.

Radix Sort Tens Digit Edited
Arranging numbers using tens place digit

After the sorting based on tens place digit is completed, we can notice that all the numbers below 100, are arranged properly among themselves.

Basically, if an array contains numbers below 100, only two iterations of arranging will sort the complete array.

Note: The numbers below 10, (having no tens place digit), are considered to have a tens place digit as 0. It makes sense, as they are to be placed before numbers having a tens place digit as 1.


Step 5: Keep performing the process until the most significant digit

In this example, the most significant digit is hundred place digit. Therefore this is the last step of the Radix Sort Algorithm.

Radix Sort Hundreds Digit Edited
Arranging numbers using hundreds place digit

As we can see, the array is now completely sorted. This is happens as soon as the array is arranged according to the most significant digit.

Before moving onto the implementation of Radix Sort, we will recommend you to study the concepts of Counting Sort Algorithm, which is used as a sub-routine for sorting the numbers based on individual digits.


Implementation of Radix Sort Algorithm in C++

#include<bits/stdc++.h>
using namespace std;

// Function that performs Radix Sort
void radix_sort(int arr[], int n){

	// Step 1: Find the maxumum element
	int maximum = arr[0];

	for(int i=1;i<n;i++){
		maximum = max(maximum, arr[i]);
	}

	// Step 2: Count the number of digits of the maximum number
	int digits = 0;

	while(maximum > 0){
		digits++;
		maximum /= 10;
	}

	// Step 3, 4, 5: Arrange the numbers on the basis of digits
	for(int i=0;i<digits;i++){

		// Units/Tens/Hundreds - used to determine which digit
		int power = pow(10, i);

		// Holds the updated array 
		int new_array[n];

		// Counting Sort Array - required for arranging digits [0-9]
		int count[10];

		// Initializing Count Array
		memset(count, 0, sizeof(count));

		// Calculating frequency of digits
		for(int j=0;j<n;j++){

			// The digit under consideration in this iteration
			int num = (arr[j]/power) % 10;

			count[num]++;
		}

		// Cumulative frequency of count array
		for(int j=1;j<10;j++){
			count[j] += count[j-1];
		}

		// Designating new positions in the updated array
		for(int j=n-1;j>=0;j--){

			// The digit under consideration in this iteration
			int num = (arr[j]/power) % 10;

			new_array[count[num]-1] = arr[j];
			count[num]--;
		}

		// Updating the original array using New Array
		for(int j=0;j<n;j++)
			arr[j] = new_array[j];
	
	}

	// Printing the sorted array
	for(int j=0;j<n;j++)
		cout<<arr[j]<<" ";

	cout<<endl;			
}

// The main function
int main(){

	// The array containing values to be sorted
	int arr[] = {15, 120, 53, 36, 167, 81, 75, 32, 9, 60};

	// Size of the array
	int n = sizeof(arr)/sizeof(n);

	// Function call for the Radix Sort Algorithm 
	radix_sort(arr, n);

	return 1;
}

OUTPUT:

9 15 32 36 53 60 75 81 120 167

Implementation of Radix Sort Algorithm in C

#include<stdio.h>

// Function that performs Radix Sort
void radix_sort(int arr[], int n){

	// Step 1: Find the maxumum element
	int maximum = arr[0];

	for(int i=1;i<n;i++){
		if(maximum < arr[i])
			maximum = arr[i];
	}

	// Step 2: Count the number of digits of the maximum number
	int digits = 0;

	while(maximum > 0){
		digits++;
		maximum /= 10;
	}

	// Units/Tens/Hundreds - used to determine which digit
	int power = 1;

	// Step 3, 4, 5: Arrange the numbers on the basis of digits
	for(int i=0;i<digits;i++){

		// Holds the updated array 
		int new_array[n];

		// Counting Sort Array - required for arranging digits [0-9]
		int count[10];

		// Initializing Count Array
		for(int j=0;j<10;j++)
			count[j] = 0;

		// Calculating frequency of digits
		for(int j=0;j<n;j++){

			// The digit under consideration in this iteration
			int num = (arr[j]/power) % 10;

			count[num]++;
		}

		// Cumulative frequency of count array
		for(int j=1;j<10;j++){
			count[j] += count[j-1];
		}

		// Designating new positions in the updated array
		for(int j=n-1;j>=0;j--){

			// The digit under consideration in this iteration
			int num = (arr[j]/power) % 10;

			new_array[count[num]-1] = arr[j];
			count[num]--;
		}

		// Updating the original array using New Array
		for(int j=0;j<n;j++)
			arr[j] = new_array[j];
		
		// Updating the digit to be considered next iteration
		power *= 10;
	}

	// Printing the sorted array
	for(int j=0;j<n;j++)
		printf("%d ", arr[j]);
	printf("\n");			
}

// The main function
int main(){

	// The array containing values to be sorted
	int arr[] = {15, 120, 53, 36, 167, 81, 75, 32, 9, 60};

	// Size of the array
	int n = sizeof(arr)/sizeof(n);

	// Function call for the Radix Sort Algorithm 
	radix_sort(arr, n);

	return 1;
}

OUTPUT:

9 15 32 36 53 60 75 81 120 167

Complexities involved in Radix Sort Algorithm

Time Complexity

Let us study the time complexity of each step in the algorithm:

  • Step 1: To find the maximum element, we linearly traverse the entire array — O(n)
  • Step 2: If we consider 'd' as the number of digits in the maximum element, then the loop for calculating the number of digits will run 'd' times — O(d)
  • Step 3, 4, 5: These steps work on the same principle of arranging numbers on the basis of digits. These steps run for 'd' times, and every time a sub-routine of “Counting Sort” is implemented — O(d * n)

Total Time Complexity: O(d * n)

Note: The loops running for Count Array does not amount to significant time complexity since a loop running for a said 10 times, is considered constant time usage.


Space Complexity

  • Step 1: We need a single variable to store the maximum element — O(1)
  • Step 2: One variable store the number of digits — O(1)
  • Step 3, 4, 5: Each iteration of “Counting Sort” requires us to create an array for storing newly arranged values — O(n).

Total Space Complexity: O(n)


Conclusion

For the past few decades, sorting techniques have been studied extensively by algorithmic experts. Radix Sort is one of the most unique non-comparative sorting algorithm.

We hope that this article was easy to understand for beginners trying to learn various sorting techniques. Feel free to ping us below for further explanations or queries.

Leave a Reply

Your email address will not be published. Required fields are marked *

close
Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages