import java.util.Collections;
import java.util.Arrays;
public class MyClass {
static void radix_sort(Integer a[]) {
radix_sort(a, 10);
}
static void radix_sort(Integer a[], int base) {
int max = Collections.max(Arrays.asList(a));
int exp, i, j, size = a.length;
for(exp=1; exp<=max; exp*=base) {
int count[] = new int[base];
int output[] = new int[size];
for(i=0; i<size; i++) count[(a[i]/exp)%base]++;
for(i=1; i<base; i++) count[i]+=count[i-1];
for(i=size-1; i>-1; i--) {
j = (a[i]/exp)%base;
output[count[j]-1] = a[i];
count[j]--;
}
for(i=0; i<size; i++) a[i]=output[i];
}
}
public static void main(String args[]) {
Integer arr[] = {9,1,22,4,0,1,22,100,10};
radix_sort(arr);
for(int x: arr) System.out.format("%d ",x);
// 0 1 1 4 9 10 22 22 100
}
}
public class MyClass {
static void radix_counting_sort(int a[], int exp, int base) {
int i, j, size = a.length;
int output[] = new int[size];
int count[] = new int[base];
for(i=0; i<size; i++) count[(a[i]/exp)%base]++;
for(i=1; i<base; i++) count[i] += count[i-1];
for(i=size-1; i>-1; i--) {
j = (a[i]/exp)%base;
output[count[j]-1] = a[i];
count[j]--;
}
for(i=0; i<size; i++) a[i] = output[i];
}
static void radix_sort(int a[], int base) {
int max = a[0];
for(int x: a) if(max<x) max=x;
for(int exp=1; max/exp>0; exp*=base) radix_counting_sort(a, exp, base);
}
static void radix_sort(int a[]) {
radix_sort(a, 10);
}
public static void main(String[] args) {
int arr[] = {9,1,22,4,0,1,22,100,10};
radix_sort(arr);
for(int x: arr) System.out.format("%d ",x);
// 0 1 1 4 9 10 22 22 100
}
}
