Counting Sort | Java implementation of Counting Sort ; The main function that sort the given string arr [ ] in alphabetical order ; The output character array that will have sorted arr ; Create a count array to store count of inidividul characters and initialize count array as 0 ; store count of each character ; Change count [ i ] so that count [ i ] now contains actual position of this character in output array ; Build the output character array To make it stable we are operating in reverse order . ; Copy the output array to arr , so that arr now contains sorted characters ; Driver method
class CountingSort { void sort ( char arr [ ] ) { int n = arr . length ; char output [ ] = new char [ n ] ; int count [ ] = new int [ 256 ] ; for ( int i = 0 ; i < 256 ; ++ i ) count [ i ] = 0 ; for ( int i = 0 ; i < n ; ++ i ) ++ count [ arr [ i ] ] ; for ( int i = 1 ; i <= 255 ; ++ i ) count [ i ] += count [ i - 1 ] ; for ( int i = n - 1 ; i >= 0 ; i -- ) { output [ count [ arr [ i ] ] - 1 ] = arr [ i ] ; -- count [ arr [ i ] ] ; } for ( int i = 0 ; i < n ; ++ i ) arr [ i ] = output [ i ] ; } public static void main ( String args [ ] ) { CountingSort ob = new CountingSort ( ) ; char arr [ ] = { ' g ' , ' e ' , ' e ' , ' k ' , ' s ' , ' f ' , ' o ' , ' r ' , ' g ' , ' e ' , ' e ' , ' k ' , ' s ' } ; ob . sort ( arr ) ; System . out . print ( " Sorted ▁ character ▁ array ▁ is ▁ " ) ; for ( int i = 0 ; i < arr . length ; ++ i ) System . out . print ( arr [ i ] ) ; } }