Added Pigeonhole Sort with its corresponding test cases

ani03sha · Anirudh Sharma · commit 9fe55c82d8ae · 2019-01-04T17:59:20.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
@@ -41,18 +41,21 @@ public Integer[] sort(Integer[] arr) {
 
         // Put each element of arr in its pigeonhole
         for (Integer integer : arr) {
-            pigeonholes[integer - min] = integer;
+            // This increment operation will count for the duplicates elements, if present
+            pigeonholes[integer - min]++;
         }
 
-        // Index for the arr
+        // Index for the original array
         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;
+        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;
             }
         }
 
diff --git a/src/test/java/src/test/java/com/sorts/PigeonholeSortTest.java b/src/test/java/src/test/java/com/sorts/PigeonholeSortTest.java
@@ -21,5 +21,10 @@ public void testPigeonholeSort() {
         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));
+
     }
 }

Original file line number	Diff line number	Diff line change
`@@ -21,5 +21,10 @@ public void testPigeonholeSort() {`
`21`	`21`	`Integer[] sorted2 = new Integer[]{-9, -5, -3, 1, 2, 4, 6, 7, 8};`
`22`	`22`	`Assert.assertArrayEquals(sorted2, pigeonholeSort.sort(unsorted2));`
`23`	`23`
	`24`	`+ // Test Case 3`
	`25`	`+ Integer[] unsorted3 = new Integer[]{-5, 1, 7, 2, -9, 6, -3, 4, 1, 8, 1, 1};`
	`26`	`+ Integer[] sorted3 = new Integer[]{-9, -5, -3, 1, 1, 1, 1, 2, 4, 6, 7, 8};`
	`27`	`+ Assert.assertArrayEquals(sorted3, pigeonholeSort.sort(unsorted3));`
	`28`	`+`
`24`	`29`	`}`
`25`	`30`	`}`