Grouping of the items with their MSB and then compare and merge. The number of digits in each element should be made same. In the below example it is 2 ie, 3 = 03 or 8 = 08.
import java.util.ArrayList;
public class RadixSort {
public void radixSort(int arr[], int maxDigits){
int exp = 1;//10^0;
for(int i =0; i < maxDigits; i++){
ArrayList bucketList[] = new ArrayList[10];
for(int k=0; k < 10; k++){
bucketList[k] = new ArrayList();
}
for(int j =0; j < arr.length; j++){
int number = (arr[j]/exp)%10;
bucketList[number].add(arr[j]);
}
exp *= 10;
int index =0;
for(int k=0; k < 10; k++){
for(int num: bucketList[k]){
arr[index] = num;
index++;
}
}
}
System.out.println("Sorted numbers");
for(int i =0; i < arr.length; i++){
System.out.print(arr[i] +", ");
}
}
public static void main(String[] argv){
int n = 5;
int arr[] = {1,4,2,3,5,10,8};
new RadixSort().radixSort(arr, 2);
}
}
0 comments :
Post a Comment