Radix Sort in C++

June 4, 2022

What is Radix Sort in C++?

Radix Sort is a Sorting algorithm that can be only applied to numeric values. This sorting technique that sorts the elements into a logical order by  grouping the individual digits of the same place value. This sorting of individual digits of same place value is done with the help of counting sort. In this article we will learn more about radix sort in C++. You can learn more about counting sort by clicking the button below.

Counting Sort
Radix sort algorithm in C++

Working of radix sort in C++

Following steps are followed to sort any numeric data in a logical order using radix sort :-

  • Take unit place digit of each element.

  • Sort the element according to their unit place using counting sort.

  • Now look upon the ten’s place digit of each element.

  • Sort the element according to their ten’s place using counting sort.

  • Repeat the step for digit of each place value.

 

Radix Sort in C++

Algorithm for radix sort in C++

Radix-Sort (array A, int n, int d)
1. for i ← 1 to d
2. do sort A to sort array A on digit i

Program for radix sort in C++

Run 
#include<iostream> 
using namespace std;

//Function to get the largest element from an array
int getMax(int array[], int n)
{
  int max = array[0];
  for (int i = 1; i < n; i++) if (array[i] > max)
      max = array[i];
  return max;
}

//Using counting sort to sort the elements in the basis of significant places
void countSort(int array[], int size, int place) 
{
  const int max = 10;
  int output[size];
  int count[max];

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

  //Calculate count of elements
  for (int i = 0; i < size; i++)
    count[(array[i] / place) % 10]++;

  //Calculating cumulative count
  for (int i = 1; i < max; i++)
    count[i] += count[i - 1];

  //Placing the elements in sorted order
  for (int i = size - 1; i >= 0; i--) 
  {
    output[count[(array[i] / place) % 10] - 1] = array[i];
    count[(array[i] / place) % 10]--;
  }

  for (int i = 0; i < size; i++)
    array[i] = output[i];
}

//Main function to implement radix sort
void radixsort(int array[], int size) 
{
  //Getting maximum element
  int max = getMax(array, size);

  //Applying counting sort to sort elements based on place value.
  for (int place = 1; max / place > 0; place *= 10)
    countSort(array, size, place);
}

//Printing an array
void display(int array[], int size) 
{
  int i;
  for (i = 0; i < size; i++)
    cout << array[i] << "\t";
  cout << endl;
}

int main() 
{
  int array[] = {112, 400, 543, 441, 678, 675, 9, 777};
  int n = sizeof(array) / sizeof(array[0]);
  cout<<"Before sorting \n";
  display(array, n);
  radixsort(array, n);
  cout<<"After sorting \n";
  display(array, n);
}
Output:
Before sorting 
112	400	543	441	678	675	9	777	
After sorting 
9	112	400	441	543	675	678	777

Time Complexity
For Radix sort in C++

Best

O(d(n + k))

Average

O(d(n + k))

Worst

O(d(n + k))

Quiz time

Quiz Time

Question 1.Which of the following sorting algorithms in its typical implementation gives best performance when applied on a sorted array?

  1. Quick Sort
  2. Heap Sort
  3. Insertion Sort
  4. Merge
Insertion sort takes linear time when input array is sorted or almost sorted. All other sorting algorithms mentioned above will take more than linear time in their typical implementation.
 
Ans. Insertion Sort (C)
 

Question 2. What is the time complexity of Build Heap operation. Which is used to create a max(or min) binary heap from a given array.?

  1. O(n)
  2. O(log n)
  3. O(nlog n)
  4. None of the above
BUILD-HEAP(A) 
    heapsize := size(A); 
    for i := floor(heapsize/2) downto 1 
        do HEAPIFY(A, i); 
    end for 
END

Although the worst case complexity looks like O(nLogn), upper bound of time complexity is O(n).

Ans: A