Sample Codes for Counting Sort in Java (eugenp#7684)

alimate · maibin · commit d3a6a7e0342f · 2019-08-30T08:49:46.000-07:00
* Added the code samples.

* Updated the Readme.
diff --git a/algorithms-sorting/README.md b/algorithms-sorting/README.md
@@ -6,3 +6,4 @@
 - [Insertion Sort in Java](https://www.baeldung.com/java-insertion-sort)
 - [Heap Sort in Java](https://www.baeldung.com/java-heap-sort)
 - [Shell Sort in Java](https://www.baeldung.com/java-shell-sort)
+- [Counting Sort in Java](https://www.baeldung.com/java-counting-sort)
diff --git a/algorithms-sorting/src/main/java/com/baeldung/algorithms/counting/CountingSort.java b/algorithms-sorting/src/main/java/com/baeldung/algorithms/counting/CountingSort.java
@@ -0,0 +1,48 @@
+package com.baeldung.algorithms.counting;
+
+import java.util.Arrays;
+import java.util.stream.IntStream;
+
+public class CountingSort {
+
+    public static int[] sort(int[] input, int k) {
+        verifyPreconditions(input, k);
+        if (input.length == 0) return input;
+
+        int[] c = countElements(input, k);
+        int[] sorted = new int[input.length];
+        for (int i = input.length - 1; i >= 0; i--) {
+            int current = input[i];
+            sorted[c[current] - 1] = current;
+            c[current] -= 1;
+        }
+
+        return sorted;
+    }
+
+    static int[] countElements(int[] input, int k) {
+        int[] c = new int[k + 1];
+        Arrays.fill(c, 0);
+        for (int i : input) {
+            c[i] += 1;
+        }
+
+        for (int i = 1; i < c.length; i++) {
+            c[i] += c[i - 1];
+        }
+        return c;
+    }
+
+    private static void verifyPreconditions(int[] input, int k) {
+        if (input == null) {
+            throw new IllegalArgumentException("Input is required");
+        }
+
+        int min = IntStream.of(input).min().getAsInt();
+        int max = IntStream.of(input).max().getAsInt();
+
+        if (min < 0 || max > k) {
+            throw new IllegalArgumentException("The input numbers should be between zero and " + k);
+        }
+    }
+}
diff --git a/algorithms-sorting/src/test/java/com/baeldung/algorithms/counting/CountingSortUnitTest.java b/algorithms-sorting/src/test/java/com/baeldung/algorithms/counting/CountingSortUnitTest.java
@@ -0,0 +1,32 @@
+package com.baeldung.algorithms.counting;
+
+import java.util.Arrays;
+
+import static org.junit.jupiter.api.Assertions.assertArrayEquals;
+
+import org.junit.jupiter.api.Test;
+
+class CountingSortUnitTest {
+
+    @Test
+    void countElements_GivenAnArray_ShouldCalculateTheFrequencyArrayAsExpected() {
+        int k = 5;
+        int[] input = { 4, 3, 2, 5, 4, 3, 5, 1, 0, 2, 5 };
+
+        int[] c = CountingSort.countElements(input, k);
+        int[] expected = { 1, 2, 4, 6, 8, 11 };
+        assertArrayEquals(expected, c);
+    }
+
+    @Test
+    void sort_GivenAnArray_ShouldSortTheInputAsExpected() {
+        int k = 5;
+        int[] input = { 4, 3, 2, 5, 4, 3, 5, 1, 0, 2, 5 };
+
+        int[] sorted = CountingSort.sort(input, k);
+
+        // Our sorting algorithm and Java's should return the same result
+        Arrays.sort(input);
+        assertArrayEquals(input, sorted);
+    }
+}
