Skip to content

Instantly share code, notes, and snippets.

@mbchoa
Created March 23, 2015 02:21
Show Gist options
  • Save mbchoa/fc919a6b4d6e112dc018 to your computer and use it in GitHub Desktop.
Save mbchoa/fc919a6b4d6e112dc018 to your computer and use it in GitHub Desktop.
Java implementation of Radix Sort assuming base 10
private static int[] radixSort(int[] unsortedArr, int digits){
for(int i = 1; i <= digits; ++i){
unsortedArr = countSort(unsortedArr, 10, (int)Math.pow(10, i));
}
return unsortedArr;
}
private static int[] countSort(int[] unsortedArr, int base, int digit){
int[] keyArray = new int[base];
for(int i = 0; i < unsortedArr.length; ++i)
keyArray[(unsortedArr[i] / (digit/base)) % base]++;
for(int j = 1; j < keyArray.length; ++j)
keyArray[j] += keyArray[j-1];
int[] sortedArr = new int[unsortedArr.length];
for(int i = unsortedArr.length-1; i >= 0; --i){
sortedArr[keyArray[(unsortedArr[i] / (digit/base)) % base]-1] = unsortedArr[i];
keyArray[(unsortedArr[i] / (digit/base)) % base] -= 1;
}
return sortedArr;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment