1 #include<iostream> 2 #include<ctime> 3 #include <stdio.h> 4 #include<cstring> 5 #include<cstdlib> 6 #include <map> 7 #include <string> 8 using namespace std; 9 // A utility function to get maximum value in arr[]10 int getMax(int arr[], int n)11 {12     int mx = arr[0];13     for (int i = 1; i < n; i++)14         if (arr[i] > mx)15             mx = arr[i];16     return mx;17 }18 19 // A function to do counting sort of arr[] according to20 // the digit represented by exp.21 void countSort(int arr[], int n, int exp)22 {23     int output[n]; // output array24     int i, count[10] = {0};25 26     // Store count of occurrences in count[]27     for (i = 0; i < n; i++)28         count[ (arr[i]/exp)%10 ]++;29 30     // Change count[i] so that count[i] now contains actual position of31     // this digit in output[]32     for (i = 1; i < 10; i++)33         count[i] += count[i-1];34 35     // Build the output array36     for (int i = n-1; i >= 0; i--) {37         output[count[(arr[i]/exp)%10]-1] = arr[i];38         count[(arr[i]/exp)%10]--;39     }40 41     // Copy the output array to arr[], so that arr[] now42     // contains sorted numbers according to curent digit43     for (i = 0; i < n; i++)44         arr[i] = output[i];45 }46 47 // The main function to that sorts arr[] of size n using Radix Sort48 void radixsort(int arr[], int n)49 {50     // Find the maximum number to know number of digits51     int m = getMax(arr, n);52 53     // Do counting sort for every digit. Note that instead of passing digit54     // number, exp is passed. exp is 10^i where i is current digit number55     for (int exp = 1; m/exp > 0; exp *= 10)56         countSort(arr, n, exp);57 }58 59 // A utility function to print an array60 void print(int arr[], int n)61 {62     for (int i = 0; i < n; i++)63         cout << arr[i] << " ";64 }65 #if TEST66 int main(){67     int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};68         int n = sizeof(arr)/sizeof(arr[0]);69         radixsort(arr, n);70         print(arr, n);71 }72 #endif