# Radix Sort – Sorting Algorithm

By | January 5, 2020

There are many sorting algorithms in Computer Science Data Structure, and most of those give the same time complexity which is O(nlogn), where n represents the total number of elements present in the given structure, and the sorting algorithms which satisfy this time complexity are Merge sort, Quick-sort, Heap sort, etc. There is another sorting algorithm Counting sort which time complexity is O(n+k), where n is the total number of elements present in the structure and k is the range of elements from 1 to k, and it can be represented as linear time complexity for a limited set of elements present in the structure.

The question is if we have a sorting algorithm that can sort elements in a linear time why don’t we use it? the answer is simple the counting sort not only depend upon the total number of elements (n) but also the range of elements (k), suppose if the range of elements becomes n2  (k =n2) the time complexity of the sorting will also become O(n2), so for small set of elements counting sort can provide linear time complexity and for high range elements, it provides exponential time complexity.

So do we have any sorting algorithms which can sort elements in linear time, the answer is Radix sort, it can sort any data type elements in linear time, and here in this article we have provided a brief introduction of Radix Sort, with its algorithm and implementation in Python and C++ language?

Radix sort is a stable Sorting algorithm that uses the element place value to sort them in either ascending or descending order. In radix sort, the place value of elements plays a vital role, to perform the sorting we start from the least significant place value which would be the value of ones and then we move toward the high significant place value.

Example:

Suppose we have an array [112, 113, 70, 23, 55, 120]

 112 113 070 023 055 120

here the largest number is 120 so we consider hundreds as the high significant place value, this means we will iterate through each element 3 times.

In the first iteration, we sort the elements according to their one place value

 070 120 112 113 023 055

In the second iteration elements will sort according to their tenth place value.

 112 113 120 023 055 170

In the third iteration, elements will sort according to their hundredth place value.

 023 055 112 113 120 170

hence we got a sorted array [23, 55, 112, 113, 120, 170]

To Understand this You can also watch this video:

1. First, we need to find the largest element of the array and considered its highest place value as the high significant place value.
2. The high significant value determines the number of iteration performed by the algorithm.
3. Once we have a highly significant value go through each significant value of the elements from low to high.
4. In radix sort, we use the counting sort technique to sort the digits at a significant place.
5. We use counting sort because for each significant place value it provides the stable sorting with O(n) time complexity.
6. Perform the counting sort for each place value from low to high until all the significant place value gets sorted.

```Radix_Sort(list)
n =total digits in maximum nunber
for i=0 to n
use Counting _Sort(array, i)

Counting_Sort(array, n)
max = largest number of nth place value
counting sort algo to sort the array according to the nth place value
```

For n number of elements present in the array with base and the d is the highest significant place value, the time complexity of Radix sort would be O(d(n+b)). For integer value where base b would be 10 and the highest significant place value becomes 6 so both d and b for integers are constant then the time complexity becomes O(n).

#### Radix Sort Program in Python

```def Counting_Sort(array, p_v):
n = len(array)
new = [1 for i in range(n)]
c = [0] * (10)
for i in range(0, n):
index = (array[i]//p_v)
c[(index)%10] += 1
for i in range(1,10):
c[i] += c[i-1]
i = n-1
while i>=0:
index = (array[i]//p_v)
new[ c[ (index)%10 ] - 1] = array[i]
c[ (index)%10 ] -= 1
i -= 1
i = 0
for i in range(0,len(array)):
array[i] = new[i]
largest_number = max(array)
place_value = 1
while largest_number/place_value > 0:
Counting_Sort(array,place_value)
place_value *= 10
array = [ 112, 113, 70, 23, 55, 120]
for i in range(len(array)):
print(array[i])
```

#### Radix Sort Program in C++

```#include<iostream.h>
#include<conio.h>
#include<stdio.h>
int max(int array[], int n)
{
int m = array[0];
for (int i = 1; i < n; i++)
{
if(array[i] > m)
m = array[i];
}
return m;
}
void Count_Sort(int array[], int n, int place_value)
{
int new_arr[100];
int i, c[10] = {0};

for(i = 0; i < n; i++)
c[ (array[i]/place_value)%10 ]++;

for(i = 1; i < 10; i++)
c[i] += c[i-1];

for(i = n - 1; i >= 0; i--)
{
new_arr[c[ (array[i]/place_value)%10 ] - 1] = array[i];
c[(array[i]/place_value)%10 ]--;
}
for (i = 0; i < n; i++)
array[i] = new_arr[i]
}
{
int m = max(array, n);
for (int p_v = 1; m/p_v > 0; p_v *= 10)
Count_Sort(array, n, p_v);
}
void show(int array[], int n)
{
for (int i = 0; i < n; i++)
cout << array[i] <<endl;
}
void main()
{
clrscr();
int array[] = {112, 113, 23, 55, 70, 120};
int n = sizeof(array)/sizeof(array[0]);
show(array, n);
getch();
}
```

23
55
70
112
113
120

#### Radix Sort Program in C

```#include <stdio.h>
int get_max(int arr[], int n)
{
int max = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > max)
max = arr[i];
return max;
}
void count_sort(int arr[], int size, int pos)
{
int output[size + 1];
int max = (arr[0] / pos) % 10;
for (int i = 1; i < size; i++)
{
if (((arr[i] / pos) % 10) > max)
max = arr[i];
}
int count[max + 1];

for (int i = 0; i < max; ++i)
count[i] = 0;

for (int i = 0; i < size; i++)
count[(arr[i] / pos) % 10]++;

for (int i = 1; i < 10; i++)
count[i] += count[i - 1];

for (int i = size - 1; i >= 0; i--)
{
output[count[(arr[i] / pos) % 10] - 1] = arr[i];
count[(arr[i] / pos) % 10]--;
}
for (int i = 0; i < size; i++)
arr[i] = output[i];
}
{
int max = get_max(arr, size);
for (int pos = 1; max / pos > 0; pos *= 10)
count_sort(arr, size, pos);
}
void show_array(int arr[], int size)
{
for (int i = 0; i < size; ++i)
{
printf("%d  ", arr[i]);
}
printf("\n");
}
int main()
{
int arr[] = {5,6,16,12,91,72,43,111,70, 200};
int n = sizeof(arr) / sizeof(arr[0]);