## 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.

## 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
{
//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);
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
```

O(d(n + k))

O(d(n + k))

## Worst

O(d(n + k))

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