Add Strand Sort (TheAlgorithms#3205)

MarcusCody · web-flow · commit b36f35907648 · 2022-08-06T20:22:42.000Z
diff --git a/src/main/java/com/thealgorithms/sorts/StrandSort.java b/src/main/java/com/thealgorithms/sorts/StrandSort.java
@@ -0,0 +1,42 @@
+package com.thealgorithms.sorts;
+import java.util.Iterator;
+import java.util.LinkedList;
+ 
+public class StrandSort{
+	// note: the input list is destroyed
+	public static <E extends Comparable<? super E>> 
+	LinkedList<E> strandSort(LinkedList<E> list){
+		if(list.size() <= 1) return list;
+ 
+		LinkedList<E> result = new LinkedList<E>();
+		while(list.size() > 0){
+			LinkedList<E> sorted = new LinkedList<E>();
+			sorted.add(list.removeFirst()); //same as remove() or remove(0)
+			for(Iterator<E> it = list.iterator(); it.hasNext(); ){
+				E elem = it.next();
+				if(sorted.peekLast().compareTo(elem) <= 0){
+					sorted.addLast(elem); //same as add(elem) or add(0, elem)
+					it.remove();
+				}
+			}
+			result = merge(sorted, result);
+		}
+		return result;
+	}
+ 
+	private static <E extends Comparable<? super E>>
+	LinkedList<E> merge(LinkedList<E> left, LinkedList<E> right){
+		LinkedList<E> result = new LinkedList<E>();
+		while(!left.isEmpty() && !right.isEmpty()){
+			//change the direction of this comparison to change the direction of the sort
+			if(left.peek().compareTo(right.peek()) <= 0)
+				result.add(left.remove());
+			else
+				result.add(right.remove());
+		}
+		result.addAll(left);
+		result.addAll(right);
+		return result;
+	}
+
+}
diff --git a/src/test/java/com/thealgorithms/sorts/StrandSortTest.java b/src/test/java/com/thealgorithms/sorts/StrandSortTest.java
@@ -0,0 +1,39 @@
+package com.thealgorithms.sorts;
+
+import org.junit.jupiter.api.Test;
+import static org.junit.jupiter.api.Assertions.*;
+
+import java.util.Arrays;
+import java.util.LinkedList;
+
+
+class StrandSortTest {
+	@Test
+	// valid test case
+	public void StrandSortNonDuplicateTest() {
+		int[] expectedArray = { 1, 2, 3, 4, 5 };
+		LinkedList<Integer> actualList = StrandSort.strandSort(new LinkedList<Integer>(Arrays.asList(3, 1, 2, 4, 5)));
+		int[] actualArray = new int[actualList.size()];
+		for (int i = 0; i < actualList.size(); i++) {
+			actualArray[i] = actualList.get(i);
+		}
+		assertArrayEquals(expectedArray, actualArray);
+
+	}
+
+	@Test
+	// valid test case
+	public void StrandSortDuplicateTest() {
+		int[] expectedArray = { 2, 2, 2, 5, 7 };
+		LinkedList<Integer> actualList = StrandSort.strandSort(new LinkedList<Integer>(Arrays.asList(7, 2, 2, 2, 5)));
+		int[] actualArray = new int[actualList.size()];
+		for (int i = 0; i < actualList.size(); i++) {
+			actualArray[i] = actualList.get(i);
+		}
+		assertArrayEquals(expectedArray, actualArray);
+
+	}
+
+}
+
+
