Repository: TheAlgorithms/Java
Pull request #5243 (2024-06-20 10:58:18)

Refactoring and code improving for StrandSort
Refactor and enhance StrandSort to align with the SortAlgorithm approach. 

Generalize the algorithm to work with any type and replace LinkedList dependencies with common List interface.

<!--
Thank you for your contribution!
In order to reduce the number of notifications sent to the maintainers, please:
- create your PR as draft, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/about-pull-requests#draft-pull-requests,
- make sure that all of the CI checks pass,
- mark your PR as ready for review, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/changing-the-stage-of-a-pull-request#marking-a-pull-request-as-ready-for-review
-->

<!-- For completed items, change [ ] to [x] -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
- [x] All new code is formatted with `clang-format -i --style=file path/to/your/file.java`


Patch:
diff --git a/src/main/java/com/thealgorithms/sorts/StrandSort.java b/src/main/java/com/thealgorithms/sorts/StrandSort.java
index 51600812..58cd3562 100644
--- a/src/main/java/com/thealgorithms/sorts/StrandSort.java
+++ b/src/main/java/com/thealgorithms/sorts/StrandSort.java
@@ -1,46 +1,79 @@
 package com.thealgorithms.sorts;
 
-import java.util.Iterator;
-import java.util.LinkedList;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
 
-public final class StrandSort {
-    private StrandSort() {
+/**
+ * StrandSort class implementing the SortAlgorithm interface using arrays.
+ */
+public final class StrandSort implements SortAlgorithm {
+
+    /**
+     * Sorts the given array using the Strand Sort algorithm.
+     *
+     * @param <T> The type of elements to be sorted, must be Comparable.
+     * @param unsorted The array to be sorted.
+     * @return The sorted array.
+     */
+    @Override
+    public <T extends Comparable<T>> T[] sort(T[] unsorted) {
+        List<T> unsortedList = new ArrayList<>(Arrays.asList(unsorted));
+        List<T> sortedList = strandSort(unsortedList);
+        return sortedList.toArray(unsorted);
     }
 
-    // note: the input list is destroyed
-    public static <E extends Comparable<? super E>> LinkedList<E> strandSort(LinkedList<E> list) {
+    /**
+     * Strand Sort algorithm that sorts a list.
+     *
+     * @param <T> The type of elements to be sorted, must be Comparable.
+     * @param list The list to be sorted.
+     * @return The sorted list.
+     */
+    private static <T extends Comparable<? super T>> List<T> strandSort(List<T> 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();
+        List<T> result = new ArrayList<>();
+        while (!list.isEmpty()) {
+            final List<T> sorted = new ArrayList<>();
+            sorted.add(list.remove(0));
+            for (int i = 0; i < list.size();) {
+                if (sorted.get(sorted.size() - 1).compareTo(list.get(i)) <= 0) {
+                    sorted.add(list.remove(i));
+                } else {
+                    i++;
                 }
             }
-            result = merge(sorted, result);
+            result = merge(result, sorted);
         }
         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());
+    /**
+     * Merges two sorted lists into one sorted list.
+     *
+     * @param <T> The type of elements to be sorted, must be Comparable.
+     * @param left The first sorted list.
+     * @param right The second sorted list.
+     * @return The merged sorted list.
+     */
+    private static <T extends Comparable<? super T>> List<T> merge(List<T> left, List<T> right) {
+        List<T> result = new ArrayList<>();
+        int i = 0;
+        int j = 0;
+        while (i < left.size() && j < right.size()) {
+            if (left.get(i).compareTo(right.get(j)) <= 0) {
+                result.add(left.get(i));
+                i++;
             } else {
-                result.add(right.remove());
+                result.add(right.get(j));
+                j++;
             }
         }
-        result.addAll(left);
-        result.addAll(right);
+        result.addAll(left.subList(i, left.size()));
+        result.addAll(right.subList(j, right.size()));
         return result;
     }
 }


Test patch:
diff --git a/src/test/java/com/thealgorithms/sorts/StrandSortTest.java b/src/test/java/com/thealgorithms/sorts/StrandSortTest.java
index 91e85c81..a7250acf 100644
--- a/src/test/java/com/thealgorithms/sorts/StrandSortTest.java
+++ b/src/test/java/com/thealgorithms/sorts/StrandSortTest.java
@@ -1,34 +1,8 @@
 package com.thealgorithms.sorts;
 
-import static org.junit.jupiter.api.Assertions.assertArrayEquals;
-
-import java.util.Arrays;
-import java.util.LinkedList;
-import org.junit.jupiter.api.Test;
-
-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);
+class StrandSortTest extends SortingAlgorithmTest {
+    @Override
+    SortAlgorithm getSortAlgorithm() {
+        return new StrandSort();
     }
 }