Added StoogeSort algorithm and JUnit Test

LesliePinto89 · LesliePinto89 · commit 7281281d3393 · 2018-11-04T17:51:27.000Z
diff --git a/src/main/java/com/sorts/StoogeSort.java b/src/main/java/com/sorts/StoogeSort.java
@@ -0,0 +1,39 @@
+package src.main.java.com.sorts;
+
+import static src.main.java.com.sorts.SortUtils.swap;
+import static src.main.java.com.sorts.SortUtils.less;
+
+public class StoogeSort {
+
+	/**
+	 * This method implements recursion StoogeSort
+	 * 
+	 * @param int[] array to store number elements
+	 * @param f first element in the array
+	 * @param l last element in the array
+	 */
+	public <T extends Comparable<T>> T[] sort(T[] arr, int f, int l) {
+
+		// Ends recursion when met
+		if (f >= l)
+			return arr;
+
+		if (less(arr[l], arr[f])) {
+			swap(arr, f, l);
+		}
+
+		if (l - f + 1 > 2) {
+			int entry = (l - f + 1) / 3;
+
+			// Does a recursive sort of the first two thirds elements
+			sort(arr, f, l - entry);
+
+			// Does a recursive sort of the last two thirds elements
+			sort(arr, f + entry, l);
+
+			// Another recursive sort first two thirds elements to confirm
+			sort(arr, f, l - entry);
+		}
+		return arr;
+	}
+}
diff --git a/src/test/java/com/sorts/StoogeSortTest.java b/src/test/java/com/sorts/StoogeSortTest.java
@@ -0,0 +1,27 @@
+package src.test.java.com.sorts;
+
+import org.junit.Assert;
+import org.junit.Test;
+import src.main.java.com.sorts.StoogeSort;
+
+public class StoogeSortTest {
+
+	@Test
+	public void stoogeSortTest() {
+		StoogeSort stoogesort = new StoogeSort();
+
+		Integer unsortedArr[] = { 2, 4, 5, 3, 1 };
+		Integer n = unsortedArr.length;
+		Integer sortedArr[] = { 1, 2, 3, 4, 5 };
+		Assert.assertArrayEquals(sortedArr, stoogesort.sort(unsortedArr, 0, n - 1));
+
+		unsortedArr = new Integer[] { -22, -34, -25, -53, -11 };
+		sortedArr = new Integer[] { -53, -34, -25, -22, -11 };
+		Assert.assertArrayEquals(sortedArr, stoogesort.sort(unsortedArr, 0, n - 1));
+		
+		Character[] unsortedCharArr = new Character[] { 'a', 'r', 'd', 'k', 'p' };
+		n = unsortedCharArr.length;
+		Character[] sortedCharArr = new Character[] { 'a', 'd', 'k', 'p', 'r' };
+		Assert.assertArrayEquals(sortedCharArr, stoogesort.sort(unsortedCharArr, 0, n - 1));
+	}
+}
