Radix Sort in C++

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.

Radix sort algorithm in C++

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.

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 for example
Radix Sort in C for example

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	

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Time and Space Complexity for Radix Sort in C++

Time Complexity of Radix Sort

Radix Sort works by sorting numbers digit by digit. It uses a stable sorting method (like Counting Sort) for each digit.

Let:

  • n = number of elements
  • k = number of digits in the largest number (for example, 802 has 3 digits)

Best Case: O(n * k)
It goes through each digit of every number, even if the data is already sorted.

Average Case: O(n * k)
It still needs to process all digits of all numbers.

Worst Case: O(n * k)
Even when the numbers are in the worst possible order, it processes all digits the same way.

So, in all cases, the time complexity is O(n * k), where k depends on the number of digits in the largest number.

Space Complexity of Radix Sort

Radix Sort needs some extra space to work:

  • An output array of size n to store results during sorting.
  • A count array of fixed size (usually 10 for base 10 numbers) to count digits.

Space Complexity: O(n + b)

Where:

  • n is the number of elements
  • b is the base (for decimal numbers, b = 10)
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

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

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription