Added Pigeonhole Sort with its corresponding test cases

ani03sha · Anirudh Sharma · commit 005380f538e9 · 2019-01-04T12:29:42.000+05:30
diff --git a/src/main/java/src/main/java/com/sorts/PigeonholeSort.java b/src/main/java/src/main/java/com/sorts/PigeonholeSort.java
@@ -0,0 +1,61 @@
+package src.main.java.com.sorts;
+
+public class PigeonholeSort {
+
+    /**
+     * This method sorts the array using Pigeonhole sort technique.
+     * <p>
+     * Pigeonhole sorting is a sorting algorithms that is suitable for sorting lists of elements where the number
+     * of elements and the number of possible key values are approximately the same.
+     * <p>
+     * It requires O(n + Range) time where n is number of elements in input array and ‘Range’ is number of possible
+     * values in array.
+     *
+     * @param arr The array to be sorted
+     * @return arr Sorted array
+     */
+    public Integer[] sort(Integer[] arr) {
+
+        // Find maximum and minimum elements in array
+        int min = arr[0];
+        int max = arr[0];
+
+        for (Integer integer : arr) {
+
+            // For minimum value
+            if (min > integer) {
+                min = integer;
+            }
+
+            // For maximum value
+            if (max < integer) {
+                max = integer;
+            }
+        }
+
+        // Range
+        int range = max - min + 1;
+
+        // Pigeonhole array
+        int[] pigeonholes = new int[range];
+
+        // Put each element of arr in its pigeonhole
+        for (Integer integer : arr) {
+            pigeonholes[integer - min] = integer;
+        }
+
+        // Index for the arr
+        int index = 0;
+
+        // Loop over pigeonhole array
+        for (int pigeonhole : pigeonholes) {
+
+            // Put non zero elements from the pigeonhole array to the current element of arr
+            if (pigeonhole != 0) {
+                arr[index++] = pigeonhole;
+            }
+        }
+
+        return arr;
+    }
+}
diff --git a/src/test/java/src/test/java/com/sorts/PigeonholeSortTest.java b/src/test/java/src/test/java/com/sorts/PigeonholeSortTest.java
@@ -0,0 +1,25 @@
+package src.test.java.com.sorts;
+
+import org.junit.Assert;
+import org.junit.Test;
+import src.main.java.com.sorts.PigeonholeSort;
+
+public class PigeonholeSortTest {
+
+    @Test
+    public void testPigeonholeSort() {
+
+        PigeonholeSort pigeonholeSort = new PigeonholeSort();
+
+        // Test Case 1
+        Integer[] unsorted1 = new Integer[]{5, 1, 7, 2, 9, 6, 3, 4, 8};
+        Integer[] sorted1 = new Integer[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
+        Assert.assertArrayEquals(sorted1, pigeonholeSort.sort(unsorted1));
+
+        // Test Case 2
+        Integer[] unsorted2 = new Integer[]{-5, 1, 7, 2, -9, 6, -3, 4, 8};
+        Integer[] sorted2 = new Integer[]{-9, -5, -3, 1, 2, 4, 6, 7, 8};
+        Assert.assertArrayEquals(sorted2, pigeonholeSort.sort(unsorted2));
+
+    }
+}
