Repository: TheAlgorithms/Java
Pull request #5745 (2024-10-13 02:58:30)

feat: Add `CountingInversions` new algorithm with Junit tests
<!--
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/5745?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 63.99%. Comparing base [(`4a03f42`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/4a03f420616a6773e9a5cdc304b1681e96d945bd?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`bc8c9ee`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/bc8c9ee31dd1e4ccedc462ca4ae3dd746d499b43?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    #5745      +/-   ##
============================================
+ Coverage     63.91%   63.99%   +0.07%     
- Complexity     4167     4176       +9     
============================================
  Files           582      583       +1     
  Lines         16302    16329      +27     
  Branches       3148     3152       +4     
============================================
+ Hits          10419    10449      +30     
+ Misses         5457     5455       -2     
+ Partials        426      425       -1     
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5745?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 19301ee3..0b34e106 100644
--- a/DIRECTORY.md
+++ b/DIRECTORY.md
@@ -251,6 +251,7 @@
           * divideandconquer
             * [BinaryExponentiation](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/divideandconquer/BinaryExponentiation.java)
             * [ClosestPair](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/divideandconquer/ClosestPair.java)
+            * [CountingInversions](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/divideandconquer/CountingInversions.java)
             * [MedianOfTwoSortedArrays](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/divideandconquer/MedianOfTwoSortedArrays.java)
             * [SkylineAlgorithm](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/divideandconquer/SkylineAlgorithm.java)
             * [StrassenMatrixMultiplication](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/divideandconquer/StrassenMatrixMultiplication.java)
@@ -833,6 +834,7 @@
           * divideandconquer
             * [BinaryExponentiationTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/divideandconquer/BinaryExponentiationTest.java)
             * [ClosestPairTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/divideandconquer/ClosestPairTest.java)
+            * [CountingInversionsTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/divideandconquer/CountingInversionsTest.java)
             * [MedianOfTwoSortedArraysTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/divideandconquer/MedianOfTwoSortedArraysTest.java)
             * [SkylineAlgorithmTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/divideandconquer/SkylineAlgorithmTest.java)
             * [StrassenMatrixMultiplicationTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/divideandconquer/StrassenMatrixMultiplicationTest.java)
diff --git a/src/main/java/com/thealgorithms/divideandconquer/CountingInversions.java b/src/main/java/com/thealgorithms/divideandconquer/CountingInversions.java
new file mode 100644
index 00000000..15c8bc33
--- /dev/null
+++ b/src/main/java/com/thealgorithms/divideandconquer/CountingInversions.java
@@ -0,0 +1,101 @@
+package com.thealgorithms.divideandconquer;
+
+/**
+ * A utility class for counting the number of inversions in an array.
+ * <p>
+ * An inversion is a pair (i, j) such that i < j and arr[i] > arr[j].
+ * This class implements a divide-and-conquer approach, similar to merge sort,
+ * to count the number of inversions efficiently.
+ * <p>
+ * Time Complexity: O(n log n)
+ * Space Complexity: O(n) (due to temporary arrays during merge step)
+ *
+ * <p>Applications:
+ * - Used in algorithms related to sorting and permutation analysis.
+ * - Helps in determining how far an array is from being sorted.
+ * - Applicable in bioinformatics and signal processing.
+ *
+ * <p>This class cannot be instantiated, as it is intended to provide
+ * only static utility methods.
+ *
+ * @author Hardvan
+ */
+public final class CountingInversions {
+    private CountingInversions() {
+    }
+
+    /**
+     * Counts the number of inversions in the given array.
+     *
+     * @param arr The input array of integers.
+     * @return The total number of inversions in the array.
+     */
+    public static int countInversions(int[] arr) {
+        return mergeSortAndCount(arr, 0, arr.length - 1);
+    }
+
+    /**
+     * Recursively divides the array into two halves, sorts them, and counts
+     * the number of inversions. Uses a modified merge sort approach.
+     *
+     * @param arr  The input array.
+     * @param left The starting index of the current segment.
+     * @param right The ending index of the current segment.
+     * @return The number of inversions within the segment [left, right].
+     */
+    private static int mergeSortAndCount(int[] arr, int left, int right) {
+        if (left >= right) {
+            return 0;
+        }
+
+        int mid = left + (right - left) / 2;
+        int inversions = 0;
+
+        inversions += mergeSortAndCount(arr, left, mid);
+        inversions += mergeSortAndCount(arr, mid + 1, right);
+        inversions += mergeAndCount(arr, left, mid, right);
+        return inversions;
+    }
+
+    /**
+     * Merges two sorted subarrays and counts the cross-inversions between them.
+     * A cross-inversion occurs when an element from the right subarray is
+     * smaller than an element from the left subarray.
+     *
+     * @param arr The input array.
+     * @param left The starting index of the first subarray.
+     * @param mid The ending index of the first subarray and midpoint of the segment.
+     * @param right The ending index of the second subarray.
+     * @return The number of cross-inversions between the two subarrays.
+     */
+    private static int mergeAndCount(int[] arr, int left, int mid, int right) {
+        int[] leftArr = new int[mid - left + 1];
+        int[] rightArr = new int[right - mid];
+
+        System.arraycopy(arr, left, leftArr, 0, mid - left + 1);
+        System.arraycopy(arr, mid + 1, rightArr, 0, right - mid);
+
+        int i = 0;
+        int j = 0;
+        int k = left;
+        int inversions = 0;
+
+        while (i < leftArr.length && j < rightArr.length) {
+            if (leftArr[i] <= rightArr[j]) {
+                arr[k++] = leftArr[i++];
+            } else {
+                arr[k++] = rightArr[j++];
+                inversions += mid + 1 - left - i;
+            }
+        }
+
+        while (i < leftArr.length) {
+            arr[k++] = leftArr[i++];
+        }
+        while (j < rightArr.length) {
+            arr[k++] = rightArr[j++];
+        }
+
+        return inversions;
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/divideandconquer/CountingInversionsTest.java b/src/test/java/com/thealgorithms/divideandconquer/CountingInversionsTest.java
new file mode 100644
index 00000000..d12614d6
--- /dev/null
+++ b/src/test/java/com/thealgorithms/divideandconquer/CountingInversionsTest.java
@@ -0,0 +1,32 @@
+package com.thealgorithms.divideandconquer;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+import org.junit.jupiter.api.Test;
+
+public class CountingInversionsTest {
+
+    @Test
+    public void testCountInversions() {
+        int[] arr = {2, 3, 8, 6, 1};
+        assertEquals(5, CountingInversions.countInversions(arr));
+    }
+
+    @Test
+    public void testNoInversions() {
+        int[] arr = {1, 2, 3, 4, 5};
+        assertEquals(0, CountingInversions.countInversions(arr));
+    }
+
+    @Test
+    public void testSingleElement() {
+        int[] arr = {1};
+        assertEquals(0, CountingInversions.countInversions(arr));
+    }
+
+    @Test
+    public void testAllInversions() {
+        int[] arr = {5, 4, 3, 2, 1};
+        assertEquals(10, CountingInversions.countInversions(arr));
+    }
+}