BAEL-3194 Radix Sort in Java (eugenp#7700)

vimde · maibin · commit f53e9e55eb3c · 2019-09-07T12:34:17.000-07:00
diff --git a/algorithms-sorting/src/main/java/com/baeldung/algorithms/radixsort/RadixSort.java b/algorithms-sorting/src/main/java/com/baeldung/algorithms/radixsort/RadixSort.java
@@ -0,0 +1,53 @@
+package com.baeldung.algorithms.radixsort;
+
+import java.util.Arrays;
+
+public class RadixSort {
+
+    public static void sort(int numbers[]) {
+        int maximumNumber = findMaximumNumberIn(numbers);
+
+        int numberOfDigits = calculateNumberOfDigitsIn(maximumNumber);
+
+        int placeValue = 1;
+
+        while (numberOfDigits-- > 0) {
+            applyCountingSortOn(numbers, placeValue);
+            placeValue *= 10;
+        }
+    }
+
+    private static void applyCountingSortOn(int[] numbers, int placeValue) {
+        int range = 10; // radix or the base
+
+        int length = numbers.length;
+        int[] frequency = new int[range];
+        int[] sortedValues = new int[length];
+
+        for (int i = 0; i < length; i++) {
+            int digit = (numbers[i] / placeValue) % range;
+            frequency[digit]++;
+        }
+
+        for (int i = 1; i < 10; i++) {
+            frequency[i] += frequency[i - 1];
+        }
+
+        for (int i = 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, length);
+    }
+
+    private static int calculateNumberOfDigitsIn(int number) {
+        return (int) Math.log10(number) + 1; // valid only if number > 0
+    }
+
+    private static int findMaximumNumberIn(int[] arr) {
+        return Arrays.stream(arr).max().getAsInt();
+    }
+
+}
diff --git a/algorithms-sorting/src/test/java/com/baeldung/algorithms/radixsort/RadixSortUnitTest.java b/algorithms-sorting/src/test/java/com/baeldung/algorithms/radixsort/RadixSortUnitTest.java
@@ -0,0 +1,16 @@
+package com.baeldung.algorithms.radixsort;
+
+import static org.junit.Assert.assertArrayEquals;
+
+import org.junit.Test;
+
+public class RadixSortUnitTest {
+
+    @Test
+    public void givenUnsortedArrayWhenRadixSortThenArraySorted() {
+        int[] numbers = { 387, 468, 134, 123, 68, 221, 769, 37, 7 };
+        RadixSort.sort(numbers);
+        int[] numbersSorted = { 7, 37, 68, 123, 134, 221, 387, 468, 769 };
+        assertArrayEquals(numbersSorted, numbers);
+    }
+}
