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

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.

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.

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. void radixsort(int arr[], int n) { 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]; } radixsort(arr, n); // Printing the sorted data. cout<<"\nSorted Data "; for (i = 0; i < n; i++) cout<<"->"<<arr[i]; return 0; }

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.

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.