**Table of Contents**show

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 ** n^{2 }** (k =

**) the time complexity of the sorting will also become O(**

*n*^{2}**), so for small set of elements counting sort can provide linear time complexity and for high range elements, it provides exponential time complexity.**

*n*^{2}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**

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:

**Radix sort Algorithm**

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

**Pseudocode for Radix Sort**

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

**Radix Sort Time Complexity**

For **n** number of elements present in the array with base **b **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).**

**Implementation of Radix Sort**

**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] def Radix_Sort(array): 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] Radix_Sort(array) 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] } void Radix_Sort(int array[], int n) { 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]); Radix_Sort(array, n); show(array, n); getch(); }

**Output:**

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]; } void Radix_Sort(int arr[], int size) { 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]); Radix_Sort(arr, n); show_array(arr, n); }

**You May Also Interested In:**