Radix Sort in C++

In this tutorial, we are going to learn Radix Sort in C++ and its implementation. Let us first understand what is Radix Sort?

In Radix Sort, first, sort the elements based on the least digit i.e. the least significant digit. These results are again sorted by the second digit. We will continue this process for all digits until we reach the most significant digits. We will use a stable sort to sort them by the last digit. In our case, we are going to use counting sort. Radix Sort is a good choice for many programs. Suppose that elements to be sorted are of base d then the time complexity is given by O(nd).

Algorithm:

1. First, we will take the least significant digit of each element.
2. Sort the elements based on that digit keeping the order of elements with the same digit.
3. Repeat the process for further digits.

Example:

Unsorted list:
10, 15, 1, 60, 5, 100, 25, 50

Sorting by the least significant digit (one’s place):
10, 60, 100, 50, 1, 15, 5, 25 

Sorting by next least significant digit (ten’s place):

100, 1, 5, 10, 15, 25, 50, 60

Sorting by next least significant digit (hundred’s place):

1, 5, 10, 15, 25, 50, 60, 100

Now we can see that after sorting all significant digit one by one, we get a sorted list.

C++ Code to apply Radix Sort

#include<bits/stdc++.h>
using namespace std;
 
// Function to get maximum value in array a[].
int getmax(int a[], int n)
{
  int max = a[0];
  for (int x=1; x<n; x++)
    if (a[x] > max)
      max = a[x];
  return max;
}
 
// Function to do counting sort according to significant digits repesented by
// exp (where exp is 10^i).
void CountSort(int a[], int n, int exp)
{  
  int result[n], i, count[10] = {0};
 
  // Counting occurence of digits
  for (i =0; i <n; i++)
    count[(a[i] / exp) % 10]++;
 
  // Changing the position of count so that it appears at actual position in result.
  for (i =1; i<10; i++)
    count[i] += count[i-1];
 
  // Resultant output array
  for (i =n-1; i>= 0; i--)
  {
    result[count[(a[i] / exp) % 10] - 1] = a[i];
    count[(a[i] / exp) % 10]--;
  }
  for (i =0; i <n; i++)
    a[i] = result[i];
}
 
// Radix Sort to sort a[] of given size.
void radixsort(int a[], int n)
{
  int exp, i;
  i = getmax(a, n);
  for (exp = 1; i/exp > 0; exp *= 10)
    CountSort(a, n, exp);
}

// Driver Program
int main()
{
  int n;
  cout<<" Enter the number of elements to be sorted: ";
  cin>>n;
    int a[n];
  
  cout<<"\n Enter the elements: ";
  for(int i =0; i <n; i++)
  {
    cin>>a[i];
  }
    radixsort(a, n);
 
  // Printing the sorted list.
  cout<<"\nSorted List: ";
  for (int i = 0; i < n; i++)
    cout<<a[i]<<", ";
  return 0;
}

 

Input:

Input:

Enter the number of elements to be sorted: 8

Enter the elements: 10 15 1 60 5 100 25 50

Output:

Output:

Sorted List: 1, 5, 10, 15, 25, 50, 60, 100

You may also learn,

Dijkstra’s shortest path algorithm in C++

Bubble Sort in C++

Do not forget to comment if you find anything wrong in the post or you want to share some information regarding the same.