Repository: TheAlgorithms/Java
Pull request #5305 (2024-07-29 19:43:42)

feat: `FlashSort` implementation
FlashSort implementation.
Adding standard test.

This PR implements this feature request https://github.com/TheAlgorithms/Java/issues/5304

<!--
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`

codecov-commenter: ## [Codecov](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5305?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) Report
All modified and coverable lines are covered by tests :white_check_mark:
> Project coverage is 41.67%. Comparing base [(`5113101`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/5113101e5dd4eb2d74a8c9f5e15b73773b974bb5?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`c9db5b0`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/c9db5b0552cd5806b53b73c846de850a1bd3726f?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

<details><summary>Additional details and impacted files</summary>


```diff
@@             Coverage Diff              @@
##             master    #5305      +/-   ##
============================================
+ Coverage     41.47%   41.67%   +0.20%     
- Complexity     2556     2577      +21     
============================================
  Files           520      521       +1     
  Lines         15447    15507      +60     
  Branches       2947     2957      +10     
============================================
+ Hits           6406     6463      +57     
- Misses         8747     8748       +1     
- Partials        294      296       +2     
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5305?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).


Patch:
diff --git a/DIRECTORY.md b/DIRECTORY.md
index 22453235..656597c3 100644
--- a/DIRECTORY.md
+++ b/DIRECTORY.md
@@ -501,6 +501,7 @@
             * [DualPivotQuickSort](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/sorts/DualPivotQuickSort.java)
             * [DutchNationalFlagSort](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/sorts/DutchNationalFlagSort.java)
             * [ExchangeSort](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/sorts/ExchangeSort.java)
+            * [FlashSort](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/sorts/FlashSort.java)
             * [GnomeSort](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/sorts/GnomeSort.java)
             * [HeapSort](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/sorts/HeapSort.java)
             * [InsertionSort](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/sorts/InsertionSort.java)
@@ -874,6 +875,7 @@
             * [DualPivotQuickSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/DualPivotQuickSortTest.java)
             * [DutchNationalFlagSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/DutchNationalFlagSortTest.java)
             * [ExchangeSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/ExchangeSortTest.java)
+            * [FlashSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/FlashSortTest.java)
             * [GnomeSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/GnomeSortTest.java)
             * [HeapSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/HeapSortTest.java)
             * [InsertionSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/InsertionSortTest.java)
diff --git a/src/main/java/com/thealgorithms/sorts/FlashSort.java b/src/main/java/com/thealgorithms/sorts/FlashSort.java
new file mode 100644
index 00000000..e8dbf8c4
--- /dev/null
+++ b/src/main/java/com/thealgorithms/sorts/FlashSort.java
@@ -0,0 +1,206 @@
+package com.thealgorithms.sorts;
+
+/**
+ * Implementation of Flash Sort algorithm that implements the SortAlgorithm interface.
+ *
+ * Sorts an array using the Flash Sort algorithm.
+ * <p>
+ * Flash Sort is a distribution sorting algorithm that partitions the data into
+ * different classes based on a classification array. It performs the sorting by
+ * first distributing the data elements into different buckets (or classes) and
+ * then permuting these buckets into the sorted order.
+ * <p>
+ * The method works as follows:
+ * <ol>
+ *     <li>Finds the minimum and maximum values in the array.</li>
+ *     <li>Initializes a classification array `L` to keep track of the number of elements in each class.</li>
+ *     <li>Computes a normalization constant `c1` to map elements into classes.</li>
+ *     <li>Classifies each element of the array into the corresponding bucket in the classification array.</li>
+ *     <li>Transforms the classification array to compute the starting indices of each bucket.</li>
+ *     <li>Permutes the elements of the array into sorted order based on the classification.</li>
+ *     <li>Uses insertion sort for the final arrangement to ensure complete sorting.</li>
+ * </ol>
+ */
+public class FlashSort implements SortAlgorithm {
+    private double classificationRatio = 0.45;
+
+    public FlashSort() {
+    }
+
+    public FlashSort(double classificationRatio) {
+        if (classificationRatio <= 0 || classificationRatio >= 1) {
+            throw new IllegalArgumentException("Classification ratio must be between 0 and 1 (exclusive).");
+        }
+        this.classificationRatio = classificationRatio;
+    }
+
+    public double getClassificationRatio() {
+        return classificationRatio;
+    }
+
+    public void setClassificationRatio(double classificationRatio) {
+        if (classificationRatio <= 0 || classificationRatio >= 1) {
+            throw new IllegalArgumentException("Classification ratio must be between 0 and 1 (exclusive).");
+        }
+        this.classificationRatio = classificationRatio;
+    }
+
+    /**
+     * Sorts an array using the Flash Sort algorithm.
+     *
+     * @param array the array to be sorted.
+     * @param <T> the type of elements to be sorted, must be comparable.
+     * @return the sorted array.
+     */
+    @Override
+    public <T extends Comparable<T>> T[] sort(T[] array) {
+        flashSort(array);
+        return array;
+    }
+
+    /**
+     * Sorts an array using the Flash Sort algorithm.
+     *
+     * @param arr the array to be sorted.
+     * @param <T> the type of elements to be sorted, must be comparable.
+     */
+    private <T extends Comparable<? super T>> void flashSort(T[] arr) {
+        if (arr.length == 0) {
+            return;
+        }
+
+        final T min = findMin(arr);
+        final int maxIndex = findMaxIndex(arr);
+
+        if (arr[maxIndex].compareTo(min) == 0) {
+            return; // All elements are the same
+        }
+
+        final int m = (int) (classificationRatio * arr.length);
+
+        final int[] classificationArray = new int[m];
+
+        final double c1 = (double) (m - 1) / arr[maxIndex].compareTo(min);
+
+        classify(arr, classificationArray, c1, min);
+
+        transform(classificationArray);
+
+        permute(arr, classificationArray, c1, min, arr.length, m);
+
+        insertionSort(arr);
+    }
+
+    /**
+     * Finds the minimum value in the array.
+     *
+     * @param arr the array to find the minimum value in.
+     * @param <T> the type of elements in the array, must be comparable.
+     * @return the minimum value in the array.
+     */
+    private <T extends Comparable<? super T>> T findMin(final T[] arr) {
+        T min = arr[0];
+        for (int i = 1; i < arr.length; i++) {
+            if (arr[i].compareTo(min) < 0) {
+                min = arr[i];
+            }
+        }
+        return min;
+    }
+
+    /**
+     * Finds the index of the maximum value in the array.
+     *
+     * @param arr the array to find the maximum value index in.
+     * @param <T> the type of elements in the array, must be comparable.
+     * @return the index of the maximum value in the array.
+     */
+    private <T extends Comparable<? super T>> int findMaxIndex(final T[] arr) {
+        int maxIndex = 0;
+        for (int i = 1; i < arr.length; i++) {
+            if (arr[i].compareTo(arr[maxIndex]) > 0) {
+                maxIndex = i;
+            }
+        }
+        return maxIndex;
+    }
+
+    /**
+     * Classifies elements of the array into the classification array classificationArray.
+     *
+     * @param arr the array to be classified.
+     * @param classificationArray the classification array holding the count of elements in each class.
+     * @param c1 the normalization constant used to map the elements to the classification array.
+     * @param min the minimum value in the array.
+     * @param <T> the type of elements in the array, must be comparable.
+     */
+    private <T extends Comparable<? super T>> void classify(final T[] arr, final int[] classificationArray, final double c1, final T min) {
+        for (int i = 0; i < arr.length; i++) {
+            int k = (int) (c1 * arr[i].compareTo(min));
+            classificationArray[k]++;
+        }
+    }
+
+    /**
+     * Transforms the classification array classificationArray into the starting index array.
+     *
+     * @param classificationArray the classification array holding the count of elements in each class.
+     */
+    private void transform(final int[] classificationArray) {
+        for (int i = 1; i < classificationArray.length; i++) {
+            classificationArray[i] += classificationArray[i - 1];
+        }
+    }
+
+    /**
+     * Permutes the array into sorted order based on the classification array classificationArray.
+     *
+     * @param arr the array to be permuted.
+     * @param classificationArray the classification array holding the count of elements in each class.
+     * @param c1 the normalization constant used to map the elements to the classification array.
+     * @param min the minimum value in the array.
+     * @param n the length of the array.
+     * @param m the number of classes in the classification array.
+     * @param <T> the type of elements in the array, must be comparable.
+     */
+    private <T extends Comparable<? super T>> void permute(final T[] arr, final int[] classificationArray, final double c1, T min, int n, int m) {
+        int move = 0;
+        int j = 0;
+        int k = m - 1;
+        T flash;
+        while (move < n - 1) {
+            while (j > classificationArray[k] - 1) {
+                j++;
+                k = (int) (c1 * arr[j].compareTo(min));
+            }
+            flash = arr[j];
+            while (j != classificationArray[k]) {
+                k = (int) (c1 * flash.compareTo(min));
+                T temp = arr[classificationArray[k] - 1];
+                arr[classificationArray[k] - 1] = flash;
+                flash = temp;
+                classificationArray[k]--;
+                move++;
+            }
+        }
+    }
+
+    /**
+     * Sorts an array using the insertion sort algorithm.
+     *
+     * @param arr the array to be sorted.
+     * @param <T> the type of elements to be sorted, must be comparable.
+     */
+    private <T extends Comparable<? super T>> void insertionSort(final T[] arr) {
+        int n = arr.length;
+        for (int i = 1; i < n; i++) {
+            T key = arr[i];
+            int j = i - 1;
+            while (j >= 0 && arr[j].compareTo(key) > 0) {
+                arr[j + 1] = arr[j];
+                j--;
+            }
+            arr[j + 1] = key;
+        }
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/sorts/FlashSortTest.java b/src/test/java/com/thealgorithms/sorts/FlashSortTest.java
new file mode 100644
index 00000000..6b1a7440
--- /dev/null
+++ b/src/test/java/com/thealgorithms/sorts/FlashSortTest.java
@@ -0,0 +1,90 @@
+package com.thealgorithms.sorts;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+
+import java.lang.reflect.Method;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.List;
+import org.junit.jupiter.api.DynamicTest;
+import org.junit.jupiter.api.Test;
+import org.junit.jupiter.api.TestFactory;
+import org.junit.jupiter.api.function.Executable;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.ValueSource;
+
+public class FlashSortTest extends SortingAlgorithmTest {
+    private final FlashSort flashSort = new FlashSort();
+
+    public FlashSort getFlashSort() {
+        return flashSort;
+    }
+
+    @Override
+    SortAlgorithm getSortAlgorithm() {
+        return getFlashSort();
+    }
+
+    @Test
+    public void testDefaultConstructor() {
+        double defaultRation = 0.45;
+        FlashSort sorter = new FlashSort();
+        assertEquals(defaultRation, sorter.getClassificationRatio());
+    }
+
+    @ParameterizedTest
+    @ValueSource(doubles = {0.1, 0.2, 0.5, 0.9})
+    public void testCustomConstructorValidRatio(double ratio) {
+        FlashSort sorter = new FlashSort(ratio);
+        assertEquals(ratio, sorter.getClassificationRatio());
+    }
+
+    @ParameterizedTest
+    @ValueSource(doubles = {0, 1, -0.1, 1.1})
+    public void testCustomConstructorInvalidRatio(double ratio) {
+        assertThrows(IllegalArgumentException.class, () -> new FlashSort(ratio));
+    }
+
+    @TestFactory
+    public Collection<DynamicTest> dynamicTestsForSorting() {
+        List<DynamicTest> dynamicTests = new ArrayList<>();
+        double[] ratios = {0.1, 0.2, 0.5, 0.9};
+
+        for (double ratio : ratios) {
+            FlashSort sorter = (FlashSort) getSortAlgorithm();
+            sorter.setClassificationRatio(ratio);
+            dynamicTests.addAll(createDynamicTestsForRatio(ratio));
+        }
+
+        return dynamicTests;
+    }
+
+    private Collection<DynamicTest> createDynamicTestsForRatio(double ratio) {
+        List<DynamicTest> dynamicTests = new ArrayList<>();
+        for (TestMethod testMethod : getTestMethodsFromSuperClass()) {
+            dynamicTests.add(DynamicTest.dynamicTest("Ratio: " + ratio + " - Test: " + testMethod.name(), testMethod.executable()));
+        }
+        return dynamicTests;
+    }
+
+    private List<TestMethod> getTestMethodsFromSuperClass() {
+        List<TestMethod> testMethods = new ArrayList<>();
+        Method[] methods = SortingAlgorithmTest.class.getDeclaredMethods();
+        for (Method method : methods) {
+            if (method.isAnnotationPresent(Test.class)) {
+                testMethods.add(new TestMethod(() -> {
+                    try {
+                        method.invoke(this);
+                    } catch (Exception e) {
+                        throw new RuntimeException(e);
+                    }
+                }, method.getName()));
+            }
+        }
+        return testMethods;
+    }
+
+    record TestMethod(Executable executable, String name) {
+    }
+}