Radix Sort – Sorting Algorithm

By | January 5, 2020
Radix Sort

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.

Vamware

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

  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.

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

Leave a Reply

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