Merge pull request TheAlgorithms#669 from ani03sha/Development

yanglbme · web-flow · commit a7a087da0c06 · 2019-01-02T22:35:53.000+08:00
Added Counting Sort and Cycle Sort
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,57 @@
+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]);
+        }
+
+        // Finding the minimum element in the array
+        int min = arr[0];
+        for (int i = 1; i < arr.length; i++) {
+            min = Math.min(min, arr[i]);
+        }
+
+        // Creating the count array - This method will store the count of each element in the unsorted array
+        int[] count = new int[max - min + 1];
+
+        // This loop will store the count of each element in the array
+        for (Integer integer : arr) {
+            count[integer - min]++;
+        }
+
+        // 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 - min] - 1] = index;
+            count[index - min]--;
+        }
+
+        // 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/main/java/src/main/java/com/sorts/CycleSort.java b/src/main/java/src/main/java/com/sorts/CycleSort.java
@@ -0,0 +1,87 @@
+package src.main.java.com.sorts;
+
+public class CycleSort {
+
+    /**
+     * @param arr Array to be sorted
+     * @param <T> Generic type
+     * @return arr Sorted array
+     */
+    public <T extends Comparable<T>> T[] sort(T[] arr) {
+
+        int n = arr.length;
+
+        // Counter for the number of memory writes
+        int count = 0;
+
+        // Traverse array and put the elements on their respective right places
+        for (int i = 0; i < n - 2; i++) {
+
+            // Initialize item as the starting point
+            T item = arr[i];
+
+            // Find the position where we want to put the item
+            // Basically we count all the smaller elements to the right of the item
+            int position = i;
+
+            for (int j = i + 1; j < n; j++) {
+                if (arr[j].compareTo(item) < 0) {
+                    position++;
+                }
+            }
+
+            // Check if the element is already at the correct position...
+            if (position == i) {
+
+                // .. then we do not have to do anything
+                continue;
+            }
+
+            // Ignore duplicate elements
+            while (item == arr[position]) {
+                position++;
+            }
+
+            // Put the elements at its right position
+            if (position != i) {
+
+                // Swap
+                T temp = item;
+                item = arr[position];
+                arr[position] = temp;
+
+                count++;
+            }
+
+            // Rotate remaining cycle
+            while (position != i) {
+                position = i;
+
+                // Find the position where we put the element
+                for (int j = i + 1; j < n; j++) {
+                    if (arr[j].compareTo(item) < 0) {
+                        position++;
+                    }
+                }
+
+                // Ignore duplicate elements
+                while (item == arr[position]) {
+                    position++;
+                }
+
+                // Put the element to its correct position
+                if (item != arr[position]) {
+                    T temp = arr[position];
+                    arr[position] = item;
+                    item = temp;
+
+                    count++;
+                }
+            }
+        }
+
+        System.out.println("Number of memory writes :: " + count);
+
+        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));
+    }
+}
diff --git a/src/test/java/src/test/java/com/sorts/CycleSortTest.java b/src/test/java/src/test/java/com/sorts/CycleSortTest.java
@@ -0,0 +1,35 @@
+package src.test.java.com.sorts;
+
+import org.junit.Assert;
+import org.junit.Test;
+import src.main.java.com.sorts.CycleSort;
+
+public class CycleSortTest {
+
+    @Test
+    public void cycleSortIntegerTest() {
+
+        CycleSort cycleSort = new CycleSort();
+
+        // Test case for integers
+        Integer[] unsortedInt = new Integer[]{5, 1, 7, 0, 2, 9, 6, 3, 4, 8};
+        Integer[] sortedInt = new Integer[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
+        Assert.assertArrayEquals(sortedInt, cycleSort.sort(unsortedInt));
+
+        // Test case for floating point numbers
+        Float[] unsortedFloat = new Float[]{6.7f, 21.1f, 0.9f, -3.2f, 5.9f, -21.3f};
+        Float[] sortedFloat = new Float[]{-21.3f, -3.2f, 0.9f, 5.9f, 6.7f, 21.1f};
+        Assert.assertArrayEquals(sortedFloat, cycleSort.sort(unsortedFloat));
+
+        // Test case for characters
+        Character[] unsortedChar = new Character[]{'c', 'a', 'b', 'A', 'C', 'B'};
+        Character[] sortedChar = new Character[]{'A', 'B', 'C', 'a', 'b', 'c'};
+        Assert.assertArrayEquals(sortedChar, cycleSort.sort(unsortedChar));
+
+        // Test case for Strings
+        String[] unsortedStr = new String[]{"Edward", "Linus", "David", "Alan", "Dennis", "Robert", "Ken"};
+        String[] sortedStr = new String[]{"Alan", "David", "Dennis", "Edward", "Ken", "Linus", "Robert"};
+        Assert.assertArrayEquals(sortedStr, cycleSort.sort(unsortedStr));
+
+    }
+}
