Radix Sort - Sorting Algorithm

    There are many sorting algorithms in data structures , and most of those give the same time complexity, which is O(n log(n)), where n represents the total number of elements present in the given structure, and some of the sorting algorithms which satisfy this time complexity are merge sort, quick sort, heap sort, and radix sort.

    There is another sorting algorithm, counting sort, whose 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 that if we have a sorting algorithm that can sort elements in a linear time then why don't we use it?

    The answer is simple; the counting sort not only depends upon the total number of elements (n) but also the range of elements (k).

    Suppose if the range of elements becomes n 2 (k = n 2 ) then the time complexity of the sorting will also become O( n 2 ). So for a 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 that can sort elements in linear time? The answer is Radix sort. It can sort elements of any data type in linear time, and here in this article, we have provided a brief introduction of Radix Sort along with its algorithm and implementation in Python and C++.

    Radix Sort

    It is a stable sorting algorithm that uses the place value of the elements to sort them in either an ascending or descending order. In the 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 a 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 ones place value.

    07 0
    12 0
    11 2
    11 3
    02 3
    05 5

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

    1 1 2
    1 1 3
    1 2 0
    0 2 3
    0 5 5
    1 7 0

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

    0 23
    0 55
    1 12
    1 13
    1 20
    1 70

    Hence, we got a sorted array [23, 55, 112, 113, 120, 170]. To understand the Radix sort better, you can also watch this YouTube video:

    Algorithm

    1. First, we need to find the largest element of the array and consider its highest place value as the high significant place value.
    2. The high significant value determines the number of iterations performed by the algorithm.
    3. Once we have the high significant value go through each significant value of the elements from low to high.
    4. In the 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 values are sorted.

    Pseudocode 

    Radix_Sort(list)
  n =total digits in maximum number 
  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

    Time Complexity

    For n number of elements present in the array with base b and d as 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])

    Output: 

    23
55
70
112
113
120

    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);
}

    Output: 

    5
6
12
16
43
70
72
91
111
200

    Conclusion

    By now, you must have known how Radix sort works. It is an important sorting algorithm that every programmer must have experience with.

    People are also reading:

    Previous Tutorial Next Tutorial