# Radix Sort Algorithm – Basics to Implementation in C/C++ 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.

### 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.

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.

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.

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.

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.

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

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

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;

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

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

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

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;

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

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.

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