TheAlgorithms · yanglbme · Jan 4, 2019 · Jan 4, 2019 · Jan 4, 2019 · Jan 4, 2019
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,56 @@
+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 = Integer.MAX_VALUE;
+        int max = Integer.MIN_VALUE;
+
+        for (Integer integer : arr) {
+            min = Math.min(min, integer);
+            max = Math.max(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) {
+            // This increment operation will count for the duplicates elements, if present
+            pigeonholes[integer - min]++;
+        }
+
+        // Index for the original array
+        int index = 0;
+
+        // Loop over pigeonhole array
+        for (int i = 0; i < range; i++) {
+            // This inner loop will execute only for those indexes in
+            // pigeonhole which are greater than zero i.e., only for those
+            // elements which are present in the original array. This also
+            // takes care of the duplicate elements
+            while (pigeonholes[i]-- > 0) {
+                arr[index++] = i + min;
+            }
+        }
+
+        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,30 @@
+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));
+
+        // Test Case 3
+        Integer[] unsorted3 = new Integer[]{-5, 1, 7, 2, -9, 6, -3, 4, 1, 8, 1, 1};
+        Integer[] sorted3 = new Integer[]{-9, -5, -3, 1, 1, 1, 1, 2, 4, 6, 7, 8};
+        Assert.assertArrayEquals(sorted3, pigeonholeSort.sort(unsorted3));
+
+    }
+}