JAVA/RadixSort.java
class RadixSort {  
  
int getMax(int a[], int n) {  
   int max = a[0];  
   for(int i = 1; i<n; i++) {  
      if(a[i] > max)  
         max = a[i];  
   }  
   return max; //maximum element from the array  
}  
  
void countingSort(int a[], int n, int place) // function to implement counting   
  
sort  
{  
   int[] output = new int[n+1];  
 int[] count = new int[10];  
  
  // Calculate count of elements  
  for (int i = 0; i < n; i++)  
    count[(a[i] / place) % 10]++;  
      
  // Calculate cumulative frequency  
  for (int i = 1; i < 10; i++)  
    count[i] += count[i - 1];  
  
  // Place the elements in sorted order  
  for (int i = n - 1; i >= 0; i--) {  
    output[count[(a[i] / place) % 10] - 1] = a[i];  
    count[(a[i] / place) % 10]--;  
  }  
  
  for (int i = 0; i < n; i++)  
    a[i] = output[i];  
}  
  
// function to implement radix sort  
void radixsort(int a[], int n) {  
   
  // get maximum element from array  
  int max = getMax(a, n);  
  
  // Apply counting sort to sort elements based on place value  
  for (int place = 1; max / place > 0; place *= 10)  
    countingSort(a, n, place);  
}  
  
// function to print array elements  
void printArray(int a[], int n) {  
  for (int i = 0; i < n; ++i)   
    System.out.print(a[i] + " ");  
}  
  
  public static void main(String args[]) {  
  int a[] = {151, 259, 360, 91, 115, 706, 34, 858, 2};  
  int n = a.length;  
  RadixSort r1 = new RadixSort();  
  System.out.print("Before sorting array elements are - \n");  
  r1.printArray(a,n);  
  r1.radixsort(a, n);  
  System.out.print("\n\nAfter applying Radix sort, the array elements are -   
  
\n");  
  r1.printArray(a, n);  
}  
  } 
