MSD ( Most Significant Digit ) Radix Sort | C ++ implementation of MSD Radix Sort of MSD Radix Sort using counting sort ( ) ; A utility function to print an array ; A utility function to get the digit at index d in a integer ; The main function to sort array using MSD Radix Sort recursively ; recursion break condition ; temp is created to easily swap strings in arr [ ] ; Store occurrences of most significant character from each integer in count [ ] ; Change count [ ] so that count [ ] now contains actual position of this digits in temp [ ] ; Build the temp ; Copy all integers of temp to arr [ ] , so that arr [ ] now contains partially sorted integers ; Recursively MSD_sort ( ) on each partially sorted integers set to sort them by their next digit ; function find the largest integer ; Main function to call MSD_sort ; Find the maximum number to know number of digits ; get the length of the largest integer ; function call ; Driver Code ; Input array ; Size of the array ; Print the unsorted array ; Function Call ; Print the sorted array
#include <iostream> NEW_LINE #include <math.h> NEW_LINE #include <unordered_map> NEW_LINE using namespace std ; void print ( int * arr , int n ) { for ( int i = 0 ; i < n ; i ++ ) { cout << arr [ i ] << " ▁ " ; } cout << endl ; } int digit_at ( int x , int d ) { return ( int ) ( x / pow ( 10 , d - 1 ) ) % 10 ; } void MSD_sort ( int * arr , int lo , int hi , int d ) { if ( hi <= lo ) { return ; } int count [ 10 + 2 ] = { 0 } ; unordered_map < int , int > temp ; for ( int i = lo ; i <= hi ; i ++ ) { int c = digit_at ( arr [ i ] , d ) ; count ++ ; } for ( int r = 0 ; r < 10 + 1 ; r ++ ) count [ r + 1 ] += count [ r ] ; for ( int i = lo ; i <= hi ; i ++ ) { int c = digit_at ( arr [ i ] , d ) ; temp [ count ++ ] = arr [ i ] ; } for ( int i = lo ; i <= hi ; i ++ ) arr [ i ] = temp [ i - lo ] ; for ( int r = 0 ; r < 10 ; r ++ ) MSD_sort ( arr , lo + count [ r ] , lo + count [ r + 1 ] - 1 , d - 1 ) ; } 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 radixsort ( int * arr , int n ) { int m = getMax ( arr , n ) ; int d = floor ( log10 ( abs ( m ) ) ) + 1 ; MSD_sort ( arr , 0 , n - 1 , d ) ; } int main ( ) { int arr [ ] = { 9330 , 9950 , 718 , 8977 , 6790 , 95 , 9807 , 741 , 8586 , 5710 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; printf ( " Unsorted ▁ array ▁ : ▁ " ) ; print ( arr , n ) ; radixsort ( arr , n ) ; printf ( " Sorted ▁ array ▁ : ▁ " ) ; print ( arr , n ) ; return 0 ; }