Added algorithm class CountingSort and its corresponding test class CountingSortTest

ani03sha · Anirudh Sharma · commit e15d329c715f · 2019-01-02T12:31:54.000+05:30
diff --git a/src/main/java/src/main/java/com/sorts/CountingSort.java b/src/main/java/src/main/java/com/sorts/CountingSort.java
@@ -0,0 +1,52 @@
+package src.main.java.com.sorts;
+
+public class CountingSort {
+
+    /**
+     * This method sorts the array using counting sort technique
+     *
+     * @param arr The array to be sorted
+     * @return arr Sorted array
+     */
+    public Integer[] sort(Integer[] arr) {
+
+        // Finding the maximum element in the array
+        int max = arr[0];
+        for (int i = 1; i < arr.length; i++) {
+            max = Math.max(max, arr[i]);
+        }
+
+        // Creating the count array - This method will store the count of each element in the unsorted array
+        int[] count = new int[max + 1];
+
+        // This loop will store the count of each element in the array
+        for (int i = 0; i < max; i++) {
+
+            count[arr[i]]++;
+        }
+
+        // This loop will replace the ith index of the count array with the sum of values at the ith and (i-1) index
+        for (int i = 1; i < count.length; i++) {
+
+            count[i] = count[i] + count[i - 1];
+        }
+
+        // This array will store the sorted array
+        Integer[] places = new Integer[arr.length];
+
+        // This loop will put the ith element at is correct position in the places array
+        for (int i = 0; i < places.length; i++) {
+
+            // Getting the value of the index - the value at the oount array index will be replaced by the value
+            // in the original array
+            int index = arr[i];
+            places[count[index] - 1] = index;
+            count[index]--;
+        }
+
+        // Copy the places array back to the original array - which will be sorted
+        System.arraycopy(places, 0, arr, 0, arr.length);
+
+        return arr;
+    }
+}
diff --git a/src/test/java/src/test/java/com/sorts/CountingSortTest.java b/src/test/java/src/test/java/com/sorts/CountingSortTest.java
@@ -0,0 +1,23 @@
+package src.test.java.com.sorts;
+
+import org.junit.Assert;
+import org.junit.Test;
+import src.main.java.com.sorts.CountingSort;
+
+public class CountingSortTest {
+
+    @Test
+    public void testCountingSort() {
+
+        CountingSort countingSort = new CountingSort();
+
+        // Unsorted integer array
+        Integer[] unsorted = new Integer[]{1, 4, 1, 2, 7, 5, 2};
+
+        // Sorted integer array
+        Integer[] sorted = new Integer[]{1, 1, 2, 2, 4, 5, 7};
+
+        // Comparing the two integer arrays
+        Assert.assertArrayEquals(sorted, countingSort.sort(unsorted));
+    }
+}
