# C++ Program to Implement Radix Sort

This is a C++ Program to Sort the Given Data using Radix sort.

Problem Description

1. In this algorithm sorting of data is done from least significant digit to most significant digit.
2. Here we need 10 different spaces labeled 0 to 9.
3. Assume we have ‘n’ number of inputs.
4. Let ‘d’ be the maximum number of digit the input data has.
5. The time complexity for radix sort is O(n*d).
6. Radix sort solves the problem of card sorting by sorting on the least significant digit first.

Problem Solution

1. Get the maximum value from the input array which has ‘d’ digits.
2. Starting from least significant digit, sort the data.
3. Take this data as input for next significant digit.
4. Run the iteration till d digit.
5. Display the result.
6. Exit.

Program/Source Code

C++ program to implement Radix Sort.
This program is successfully run on Dev-C++ using TDM-GCC 4.9.2 MinGW compiler on a Windows system.

```#include <iostream>

using namespace std;

// Get maximum value from array.
int getMax(int arr[], int n)
{
int max = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > max)
max = arr[i];
return max;
}

// Count sort of arr[].
void countSort(int arr[], int n, int exp)
{
// Count[i] array will be counting the number of array values having that 'i' digit at their (exp)th place.
int output[n], i, count[10] = {0};

// Count the number of times each digit occurred at (exp)th place in every input.
for (i = 0; i < n; i++)
count[(arr[i] / exp) % 10]++;

// Calculating their cumulative count.
for (i = 1; i < 10; i++)
count[i] += count[i-1];

// Inserting values according to the digit '(arr[i] / exp) % 10' fetched into count[(arr[i] / exp) % 10].
for (i = n - 1; i >= 0; i--)
{
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}

// Assigning the result to the arr pointer of main().
for (i = 0; i < n; i++)
arr[i] = output[i];
}

// Sort arr[] of size n using Radix Sort.
{
int exp, m;
m = getMax(arr, n);

// Calling countSort() for digit at (exp)th place in every input.
for (exp = 1; m/exp > 0; exp *= 10)
countSort(arr, n, exp);
}

int main()
{
int n, i;
cout<<"\nEnter the number of data element to be sorted: ";
cin>>n;

int arr[n];
for(i = 0; i < n; i++)
{
cout<<"Enter element "<<i+1<<": ";
cin>>arr[i];
}

// Printing the sorted data.
cout<<"\nSorted Data ";
for (i = 0; i < n; i++)
cout<<"->"<<arr[i];
return 0;
}```
Program Explanation

1. Take input of data.
2. Get the maximum of input data.
3. Run the countSort() till (m/exp) > 0.
4. Sort the data on the basis of the digit at (exp)th place.
5. Assign the sorted data back to arr[] array.
6. Check the condition in step 3.
7. If false, print the sorted output.
8. Exit.

Runtime Test Cases
```
Enter the number of data element to be sorted: 10
Enter element 1: 886
Enter element 2: 542
Enter element 3: 12
Enter element 4: 3
Enter element 5: 96
Enter element 6: 1125
Enter element 7: 54
Enter element 8: 129
Enter element 9: 3125
Enter element 10: 1

Sorted Data ->1->3->12->54->96->129->542->886->1125->3125```

Sanfoundry Global Education & Learning Series – C++ Algorithms.
To practice all C++ Algorithms, here is complete set of 1000 C++ Algorithms.

If you find any mistake above, kindly email to [email protected]