Add Wigglesort (TheAlgorithms#3032)

BranAndSceolan · Antonia Strack · siriak · web-flow · commit 99ff5163e3cd · 2022-04-25T16:54:33.000+03:00
Co-authored-by: Antonia Strack &lt;antonia.strack@thm.mni.de&gt;
Co-authored-by: Andrii Siriak &lt;siryaka@gmail.com&gt;
diff --git a/src/main/java/com/thealgorithms/sorts/WiggleSort.java b/src/main/java/com/thealgorithms/sorts/WiggleSort.java
@@ -0,0 +1,82 @@
+package com.thealgorithms.sorts;
+
+import java.util.Arrays;
+
+import static com.thealgorithms.maths.Ceil.ceil;
+import static com.thealgorithms.maths.Floor.floor;
+import static com.thealgorithms.searches.QuickSelect.select;
+
+/**
+ * A wiggle sort implementation based on John L.s' answer in
+ * https://cs.stackexchange.com/questions/125372/how-to-wiggle-sort-an-array-in-linear-time-complexity
+ * Also have a look at: https://cs.stackexchange.com/questions/125372/how-to-wiggle-sort-an-array-in-linear-time-complexity?noredirect=1&lq=1
+ * Not all arrays are wiggle-sortable. This algorithm will find some obviously not wiggle-sortable arrays and throw an error,
+ * but there are some exceptions that won't be caught, for example [1, 2, 2].
+ */
+public class WiggleSort implements SortAlgorithm {
+    @Override
+    public <T extends Comparable<T>> T[] sort(T[] unsorted) {
+        return wiggleSort(unsorted);
+    }
+
+    private int mapIndex(int index, int n) {
+        return ((2 * index + 1) % (n | 1));
+    }
+
+    /**
+     * Modified Dutch National Flag Sort. See also: sorts/DutchNationalFlagSort
+     *
+     * @param sortThis array to sort into group "greater", "equal" and "smaller" than median
+     * @param median   defines the groups
+     * @param <T>      extends interface Comparable
+     */
+    private <T extends Comparable<T>> void triColorSort(T[] sortThis, T median) {
+        int n = sortThis.length;
+        int i = 0;
+        int j = 0;
+        int k = n - 1;
+        while (j <= k) {
+            if (0 < sortThis[mapIndex(j, n)].compareTo(median)) {
+                SortUtils.swap(sortThis, mapIndex(j, n), mapIndex(i, n));
+                i++;
+                j++;
+            } else if (0 > sortThis[mapIndex(j, n)].compareTo(median)) {
+                SortUtils.swap(sortThis, mapIndex(j, n), mapIndex(k, n));
+                k--;
+            } else {
+                j++;
+            }
+        }
+    }
+
+    private <T extends Comparable<T>> T[] wiggleSort(T[] sortThis) {
+        // find the median using quickSelect (if the result isn't in the array, use the next greater value)
+        T median;
+
+        median = select(Arrays.<T>asList(sortThis), (int) floor(sortThis.length / 2.0));
+
+        int numMedians = 0;
+
+        for (T sortThi : sortThis) {
+            if (0 == sortThi.compareTo(median)) {
+                numMedians++;
+            }
+        }
+        // added condition preventing off-by-one errors for odd arrays.
+        // https://cs.stackexchange.com/questions/150886/how-to-find-wiggle-sortable-arrays-did-i-misunderstand-john-l-s-answer?noredirect=1&lq=1
+        if (sortThis.length % 2 == 1 && numMedians == ceil(sortThis.length / 2.0)) {
+            T smallestValue = select(Arrays.asList(sortThis), 0);
+            if (!(0 == smallestValue.compareTo(median))) {
+                throw new IllegalArgumentException("For odd Arrays if the median appears ceil(n/2) times, " +
+                        "the median has to be the smallest values in the array.");
+            }
+        }
+        if (numMedians > ceil(sortThis.length / 2.0)) {
+            throw new IllegalArgumentException("No more than half the number of values may be the same.");
+
+        }
+
+        triColorSort(sortThis, median);
+        return sortThis;
+    }
+}
diff --git a/src/test/java/com/thealgorithms/sorts/WiggleSortTest.java b/src/test/java/com/thealgorithms/sorts/WiggleSortTest.java
@@ -0,0 +1,75 @@
+package com.thealgorithms.sorts;
+
+import org.junit.jupiter.api.Test;
+
+import java.util.Arrays;
+
+import static org.junit.jupiter.api.Assertions.assertArrayEquals;
+
+
+public class WiggleSortTest {
+    @Test
+    void WiggleTestNumbersEven(){
+        WiggleSort wiggleSort = new WiggleSort();
+        Integer[] values = {1, 2, 3, 4};
+        Integer[] result = {1, 4, 2, 3};
+        wiggleSort.sort(values);
+        assertArrayEquals(values, result);
+    }
+
+    @Test
+    void WiggleTestNumbersOdd(){
+        WiggleSort wiggleSort = new WiggleSort();
+        Integer[] values = {1, 2, 3, 4, 5};
+        Integer[] result = {3, 5, 1, 4, 2};
+        wiggleSort.sort(values);
+        assertArrayEquals(values, result);
+
+    }
+
+    @Test
+    void WiggleTestNumbersOddDuplicates(){
+        WiggleSort wiggleSort = new WiggleSort();
+        Integer[] values = {7, 2, 2, 2, 5};
+        Integer[] result = {2, 7, 2, 5, 2};
+        wiggleSort.sort(values);
+        assertArrayEquals(values, result);
+    }
+
+    @Test
+    void WiggleTestNumbersOddMultipleDuplicates(){
+        WiggleSort wiggleSort = new WiggleSort();
+        Integer[] values = {1, 1, 2, 2, 5};
+        Integer[] result = {2, 5, 1, 2, 1};
+        wiggleSort.sort(values);
+        assertArrayEquals(values, result);
+    }
+
+    @Test
+    void WiggleTestNumbersEvenMultipleDuplicates(){
+        WiggleSort wiggleSort = new WiggleSort();
+        Integer[] values = {1, 1, 2, 2, 2, 5};
+        Integer[] result = {2, 5, 1, 2, 1, 2};
+        wiggleSort.sort(values);
+        System.out.println(Arrays.toString(values));
+        assertArrayEquals(values, result);
+    }
+
+    @Test
+    void WiggleTestNumbersEvenDuplicates(){
+        WiggleSort wiggleSort = new WiggleSort();
+        Integer[] values = {1, 2, 4, 4};
+        Integer[] result = {1, 4, 2, 4};
+        wiggleSort.sort(values);
+        assertArrayEquals(values, result);
+    }
+
+    @Test
+    void WiggleTestStrings(){
+        WiggleSort wiggleSort = new WiggleSort();
+        String[] values = {"a", "b", "d", "c"};
+        String[] result = {"a", "d", "b", "c"};
+        wiggleSort.sort(values);
+        assertArrayEquals(values, result);
+    }
+}
