Radix Sort | C ++ implementation of Radix Sort ; A utility function to get maximum value in arr [ ] ; A function to do counting sort of arr [ ] according to the digit represented by exp . ; output array ; Store count of occurrences in count [ ] ; Change count [ i ] so that count [ i ] now contains actual position of this digit in output [ ] ; Build the output array ; Copy the output array to arr [ ] , so that arr [ ] now contains sorted numbers according to current digit ; The main function to that sorts arr [ ] of size n using Radix Sort ; Find the maximum number to know number of digits ; Do counting sort for every digit . Note that instead of passing digit number , exp is passed . exp is 10 ^ i where i is current digit number ; A utility function to print an array ; Driver Code ; Function Call
#include <iostream> NEW_LINE using namespace std ; int getMax ( int arr [ ] , int n ) { int mx = arr [ 0 ] ; for ( int i = 1 ; i < n ; i ++ ) if ( arr [ i ] > mx ) mx = arr [ i ] ; return mx ; } void countSort ( int arr [ ] , int n , int exp ) { int output [ n ] ; int i , count [ 10 ] = { 0 } ; for ( i = 0 ; i < n ; i ++ ) count [ ( arr [ i ] / exp ) % 10 ] ++ ; for ( i = 1 ; i < 10 ; i ++ ) count [ i ] += count [ i - 1 ] ; for ( i = n - 1 ; i >= 0 ; i -- ) { output [ count [ ( arr [ i ] / exp ) % 10 ] - 1 ] = arr [ i ] ; count [ ( arr [ i ] / exp ) % 10 ] -- ; } for ( i = 0 ; i < n ; i ++ ) arr [ i ] = output [ i ] ; } void radixsort ( int arr [ ] , int n ) { int m = getMax ( arr , n ) ; for ( int exp = 1 ; m / exp > 0 ; exp *= 10 ) countSort ( arr , n , exp ) ; } void print ( int arr [ ] , int n ) { for ( int i = 0 ; i < n ; i ++ ) cout << arr [ i ] << " ▁ " ; } int main ( ) { int arr [ ] = { 170 , 45 , 75 , 90 , 802 , 24 , 2 , 66 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; radixsort ( arr , n ) ; print ( arr , n ) ; return 0 ; }