RadixSort.java

/**
 * An implementation of Radix Sort.
 *
 * <p>See https://en.wikipedia.org/wiki/Radix_sort for details on runtime and complexity Radix sorts
 * operates in O(nw) time, where n is the number of keys, and w is the key length where w is
 * constant on primitive types like Integer which gives it a better performance than other
 * compare-based sort algorithms, like i.e. QuickSort
 *
 * <p>Time Complexity: O(nw)
 *
 * @author EAlexa
 */

package Sorting;

public class RadixSort {

 static int getMax(int[] array) {
 int max = array[0];
 for (int i = 0; i < array.length; i++) {
 if (array[i] > max) {
 max = array[i];
 }
 }
 return max;
 }

 static int calculateNumberOfDigits(int number) {
 return (int) Math.log10(number) + 1;
 }

 // Requires all numbers to be greater than or equal to 1
 public static void radixSort(int[] numbers) {
 if (numbers == null || numbers.length <= 1) {
 return;
 }
 int maximum = getMax(numbers);
 int numberOfDigits = calculateNumberOfDigits(maximum);
 int placeValue = 1;
 while (numberOfDigits-- > 0) {
 countSort(numbers, placeValue);
 placeValue *= 10;
 }
 }

 private static void countSort(int[] numbers, int placeValue) {
 int range = 10;

 int[] frequency = new int[range];
 int[] sortedValues = new int[numbers.length];

 for (int i = 0; i < numbers.length; i++) {
 int digit = (numbers[i] / placeValue) % range;
 frequency[digit]++;
 }

 for (int i = 1; i < range; i++) {
 frequency[i] += frequency[i - 1];
 }

 for (int i = numbers.length - 1; i >= 0; i--) {
 int digit = (numbers[i] / placeValue) % range;
 sortedValues[frequency[digit] - 1] = numbers[i];
 frequency[digit]--;
 }

 System.arraycopy(sortedValues, 0, numbers, 0, numbers.length);
 }


 public static void main(String[] args) {
 int[] numbers = {387, 468, 134, 123, 68, 221, 769, 37, 7, 890, 1, 587};
 radixSort(numbers);
 // Prints:
 // [1, 7, 37, 68, 123, 134, 221, 387, 468, 587, 769, 890]
 System.out.println(java.util.Arrays.toString(numbers));
 }
}