Repository: TheAlgorithms/Java
Pull request #5244 (2024-06-20 18:47:50)

Improving BitonicSort
The previous sorting algorithm only worked with arrays whose sizes were powers of two. This issue has been fixed.

Additionally, the code has been refactored to follow a common approach, and tests for the sort function have been added.

<!--
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`

alxkm: There are issues with the build, not related to any recent code changes. The problem seems to be with the Codecov tool.
vil02: > There are issues with the build, not related to any recent code changes. The problem seems to be with the Codecov tool.

Codecov behaves strange for few days.
vil02: > The same for codecov. "Failed to properly create report: The process '/home/runner/work/_actions/codecov/codecov-action/v4/dist/codecov' failed with exit code 1"

It seems to be relates to codecov/codecov-action#1487.
codecov-commenter: ## [Codecov](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5244?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:
> Please [upload](https://docs.codecov.com/docs/codecov-uploader) report for BASE (`master@15d2e70`). [Learn more](https://docs.codecov.io/docs/error-reference?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#section-missing-base-commit) about missing BASE report.

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


```diff
@@            Coverage Diff            @@
##             master    #5244   +/-   ##
=========================================
  Coverage          ?   39.73%           
  Complexity        ?     2435           
=========================================
  Files             ?      517           
  Lines             ?    15515           
  Branches          ?     2958           
=========================================
  Hits              ?     6165           
  Misses            ?     9060           
  Partials          ?      290           
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5244?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).

vil02: I cannot merge it now, because the _upload to codecov_ fails. I will rerun the build in a while, so maybe it will pass.

Patch:
diff --git a/src/main/java/com/thealgorithms/sorts/BitonicSort.java b/src/main/java/com/thealgorithms/sorts/BitonicSort.java
index b4b26299..90d20481 100644
--- a/src/main/java/com/thealgorithms/sorts/BitonicSort.java
+++ b/src/main/java/com/thealgorithms/sorts/BitonicSort.java
@@ -1,79 +1,112 @@
 package com.thealgorithms.sorts;
 
-/* Java program for Bitonic Sort. Note that this program
-works only when size of input is a power of 2. */
-public class BitonicSort {
-
-    /* The parameter dir indicates the sorting direction,
-  ASCENDING or DESCENDING; if (a[i] > a[j]) agrees
-  with the direction, then a[i] and a[j] are
-  interchanged. */
-    void compAndSwap(int[] a, int i, int j, int dir) {
-        if ((a[i] > a[j] && dir == 1) || (a[i] < a[j] && dir == 0)) {
-            // Swapping elements
-            int temp = a[i];
-            a[i] = a[j];
-            a[j] = temp;
-        }
+import java.util.Arrays;
+import java.util.function.BiPredicate;
+
+/**
+ * BitonicSort class implements the SortAlgorithm interface using the bitonic sort technique.
+ */
+public class BitonicSort implements SortAlgorithm {
+    private enum Direction {
+        DESCENDING,
+        ASCENDING,
     }
 
-    /* It recursively sorts a bitonic sequence in ascending
-  order, if dir = 1, and in descending order otherwise
-  (means dir=0). The sequence to be sorted starts at
-  index position low, the parameter cnt is the number
-  of elements to be sorted.*/
-    void bitonicMerge(int[] a, int low, int cnt, int dir) {
-        if (cnt > 1) {
-            int k = cnt / 2;
-            for (int i = low; i < low + k; i++) {
-                compAndSwap(a, i, i + k, dir);
-            }
-            bitonicMerge(a, low, k, dir);
-            bitonicMerge(a, low + k, k, dir);
+    /**
+     * Sorts the given array using the Bitonic Sort algorithm.
+     *
+     * @param <T> the type of elements in the array, which must implement the Comparable interface
+     * @param array the array to be sorted
+     * @return the sorted array
+     */
+    @Override
+    public <T extends Comparable<T>> T[] sort(T[] array) {
+        if (array.length == 0) {
+            return array;
         }
+
+        final int paddedSize = nextPowerOfTwo(array.length);
+        T[] paddedArray = Arrays.copyOf(array, paddedSize);
+
+        // Fill the padded part with a maximum value
+        final T maxValue = max(array);
+        Arrays.fill(paddedArray, array.length, paddedSize, maxValue);
+
+        bitonicSort(paddedArray, 0, paddedSize, Direction.ASCENDING);
+        return Arrays.copyOf(paddedArray, array.length);
     }
 
-    /* This funcion first produces a bitonic sequence by
-  recursively sorting its two halves in opposite sorting
-  orders, and then calls bitonicMerge to make them in
-  the same order */
-    void bitonicSort(int[] a, int low, int cnt, int dir) {
+    private <T extends Comparable<T>> void bitonicSort(final T[] array, final int low, final int cnt, final Direction direction) {
         if (cnt > 1) {
-            int k = cnt / 2;
+            final int k = cnt / 2;
 
-            // sort in ascending order since dir here is 1
-            bitonicSort(a, low, k, 1);
+            // Sort first half in ascending order
+            bitonicSort(array, low, k, Direction.ASCENDING);
 
-            // sort in descending order since dir here is 0
-            bitonicSort(a, low + k, k, 0);
+            // Sort second half in descending order
+            bitonicSort(array, low + k, cnt - k, Direction.DESCENDING);
 
-            // Will merge whole sequence in ascending order
-            // since dir=1.
-            bitonicMerge(a, low, cnt, dir);
+            // Merge the whole sequence in ascending order
+            bitonicMerge(array, low, cnt, direction);
         }
     }
 
-    /*Caller of bitonicSort for sorting the entire array
-  of length N in ASCENDING order */
-    void sort(int[] a, int n, int up) {
-        bitonicSort(a, 0, n, up);
+    /**
+     * Merges the bitonic sequence in the specified direction.
+     *
+     * @param <T> the type of elements in the array, which must be Comparable
+     * @param array the array containing the bitonic sequence to be merged
+     * @param low the starting index of the sequence to be merged
+     * @param cnt the number of elements in the sequence to be merged
+     * @param direction the direction of sorting
+     */
+    private <T extends Comparable<T>> void bitonicMerge(T[] array, int low, int cnt, Direction direction) {
+        if (cnt > 1) {
+            final int k = cnt / 2;
+
+            final BiPredicate<T, T> areSorted = (direction == Direction.ASCENDING) ? (a, b) -> a.compareTo(b) < 0 : (a, b) -> a.compareTo(b) > 0;
+            for (int i = low; i < low + k; i++) {
+                if (!areSorted.test(array[i], array[i + k])) {
+                    SortUtils.swap(array, i, i + k);
+                }
+            }
+
+            bitonicMerge(array, low, k, direction);
+            bitonicMerge(array, low + k, cnt - k, direction);
+        }
     }
 
-    /* A utility function to print array of size n */
-    static void printArray(int[] arr) {
-        int n = arr.length;
-        for (int i = 0; i < n; ++i) {
-            System.out.print(arr[i] + " ");
+    /**
+     * Finds the next power of two greater than or equal to the given number.
+     *
+     * @param n the number
+     * @return the next power of two
+     */
+    private static int nextPowerOfTwo(int n) {
+        int count = 0;
+
+        // First n in the below condition is for the case where n is 0
+        if ((n & (n - 1)) == 0) {
+            return n;
+        }
+
+        while (n != 0) {
+            n >>= 1;
+            count += 1;
         }
-        System.out.println();
+
+        return 1 << count;
     }
 
-    public static void main(String[] args) {
-        int[] a = {3, 7, 4, 8, 6, 2, 1, 5};
-        int up = 1;
-        BitonicSort ob = new BitonicSort();
-        ob.sort(a, a.length, up);
-        System.out.println("\nSorted array");
-        printArray(a);
+    /**
+     * Finds the maximum element in the given array.
+     *
+     * @param <T> the type of elements in the array, which must implement the Comparable interface
+     * @param array the array to be searched
+     * @return the maximum element in the array
+     * @throws IllegalArgumentException if the array is null or empty
+     */
+    private static <T extends Comparable<T>> T max(final T[] array) {
+        return Arrays.stream(array).max(Comparable::compareTo).orElseThrow();
     }
 }


Test patch:
diff --git a/src/test/java/com/thealgorithms/sorts/BitonicSortTest.java b/src/test/java/com/thealgorithms/sorts/BitonicSortTest.java
new file mode 100644
index 00000000..60c4bbe9
--- /dev/null
+++ b/src/test/java/com/thealgorithms/sorts/BitonicSortTest.java
@@ -0,0 +1,8 @@
+package com.thealgorithms.sorts;
+
+public class BitonicSortTest extends SortingAlgorithmTest {
+    @Override
+    SortAlgorithm getSortAlgorithm() {
+        return new BitonicSort();
+    }
+}