Radix Sort in Java
Below is an example of the Radix Sort algorithm in Java. See the Radix Sort page for more information and implementations.
radix-sort in Java
class RadixSort {
public static void main(String[] args)
{
int[] array1 = {12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8};
int[] array2 = {2, 1, 5, 2, 9, 1, 2, 3, 3, 4, 4, 5, 6, 7, 8};
RadixSort radixSort = new RadixSort();
radixSort.sort(array1);
radixSort.sort(array2);
System.out.println(java.util.Arrays.toString(array1));
System.out.println(java.util.Arrays.toString(array2));
}
void sort(int[] array)
{
// get the largest number to know how many place values we need to sort
int maxValue = array[0];
for (int i = 1; i < array.length; i++)
if (array[i] > maxValue)
maxValue = array[i];
// sort the array at each placeValue
for (int placeValue = 1; maxValue / placeValue > 0; placeValue *= 10)
countingSort(array, placeValue);
}
private void countingSort(int[] array, int placeValue)
{
// step 1: create an empty array that will store the sorted version of the array
int[] output = new int[array.length];
// step 2: create an empty array that will track the placeValue frequency
int[] placeValueFrequency = new int[10];
// step 3: find the amount of times the array has a value in the placeValue we're searching for
for (int i = 0; i < array.length; i++)
{
int value = (array[i] / placeValue) % 10;
placeValueFrequency[value]++;
}
// step 4: reposition the indexes so that the indexes with smaller placeValues are moved to the beginning of the array
for (int i = 1; i < 10; i++)
placeValueFrequency[i] += placeValueFrequency[i - 1];
// step 5: starting from the end of the array, add each index index from the original array to the output array
// the frequency - 1 of the value in the current placeValue will represent the index to place the original index
for (int i = array.length - 1; i >= 0; i--)
{
int value = (array[i] / placeValue) % 10; // the value of the current placeValue
output[placeValueFrequency[value] - 1] = array[i];
placeValueFrequency[value]--;
}
// step 6: copy the more sorted version of the array back into the original array
for (int i = 0; i < array.length; i++)
array[i] = output[i];
}
}