Repository: TheAlgorithms/Java
Pull request #5374 (2024-08-23 21:07:41)

refactor: `FindKthNumber`
Improving the code to make it more readable.
Adding additional tests to this algorithm.

<!--
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/5374?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 46.48%. Comparing base [(`ce4eb55`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/ce4eb55e0e7c5216e2cba53217627f6bbe8b5083?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`5048c2c`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/5048c2cbe20efc169179c02233bacef2ce783b32?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    #5374      +/-   ##
============================================
+ Coverage     46.26%   46.48%   +0.22%     
- Complexity     2866     2878      +12     
============================================
  Files           525      525              
  Lines         15410    15397      -13     
  Branches       2916     2912       -4     
============================================
+ Hits           7130     7158      +28     
+ Misses         7981     7941      -40     
+ Partials        299      298       -1     
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5374?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/src/main/java/com/thealgorithms/maths/FindKthNumber.java b/src/main/java/com/thealgorithms/maths/FindKthNumber.java
index daea3f96..a9b26767 100644
--- a/src/main/java/com/thealgorithms/maths/FindKthNumber.java
+++ b/src/main/java/com/thealgorithms/maths/FindKthNumber.java
@@ -1,10 +1,9 @@
 package com.thealgorithms.maths;
 
-import java.util.Arrays;
 import java.util.Random;
 
 /**
- * use quick sort algorithm to get kth largest or kth smallest element in given array
+ * Use a quicksort-based approach to identify the k-th largest or k-th max element within the provided array.
  */
 public final class FindKthNumber {
     private FindKthNumber() {
@@ -12,66 +11,55 @@ public final class FindKthNumber {
 
     private static final Random RANDOM = new Random();
 
-    public static void main(String[] args) {
-        /* generate an array with random size and random elements */
-        int[] nums = generateArray(100);
-
-        /* get 3th largest element */
-        int kth = 3;
-        int kthMaxIndex = nums.length - kth;
-        int targetMax = findKthMax(nums, kthMaxIndex);
-
-        /* get 3th smallest element */
-        int kthMinIndex = kth - 1;
-        int targetMin = findKthMax(nums, kthMinIndex);
+    public static int findKthMax(int[] array, int k) {
+        if (k <= 0 || k > array.length) {
+            throw new IllegalArgumentException("k must be between 1 and the size of the array");
+        }
 
-        Arrays.sort(nums);
-        assert nums[kthMaxIndex] == targetMax;
-        assert nums[kthMinIndex] == targetMin;
+        // Convert k-th largest to index for QuickSelect
+        return quickSelect(array, 0, array.length - 1, array.length - k);
     }
 
-    private static int[] generateArray(int capacity) {
-        int size = RANDOM.nextInt(capacity) + 1;
-        int[] array = new int[size];
-
-        for (int i = 0; i < size; i++) {
-            array[i] = RANDOM.nextInt() % 100;
+    private static int quickSelect(int[] array, int left, int right, int kSmallest) {
+        if (left == right) {
+            return array[left];
         }
-        return array;
-    }
 
-    private static int findKthMax(int[] nums, int k) {
-        int start = 0;
-        int end = nums.length;
-        while (start < end) {
-            int pivot = partition(nums, start, end);
-            if (k == pivot) {
-                return nums[pivot];
-            } else if (k > pivot) {
-                start = pivot + 1;
-            } else {
-                end = pivot;
-            }
+        // Randomly select a pivot index
+        int pivotIndex = left + RANDOM.nextInt(right - left + 1);
+        pivotIndex = partition(array, left, right, pivotIndex);
+
+        if (kSmallest == pivotIndex) {
+            return array[kSmallest];
+        } else if (kSmallest < pivotIndex) {
+            return quickSelect(array, left, pivotIndex - 1, kSmallest);
+        } else {
+            return quickSelect(array, pivotIndex + 1, right, kSmallest);
         }
-        return -1;
     }
 
-    private static int partition(int[] nums, int start, int end) {
-        int pivot = nums[start];
-        int j = start;
-        for (int i = start + 1; i < end; i++) {
-            if (nums[i] < pivot) {
-                j++;
-                swap(nums, i, j);
+    private static int partition(int[] array, int left, int right, int pivotIndex) {
+        int pivotValue = array[pivotIndex];
+        // Move pivot to end
+        swap(array, pivotIndex, right);
+        int storeIndex = left;
+
+        // Move all smaller elements to the left
+        for (int i = left; i < right; i++) {
+            if (array[i] < pivotValue) {
+                swap(array, storeIndex, i);
+                storeIndex++;
             }
         }
-        swap(nums, start, j);
-        return j;
+
+        // Move pivot to its final place
+        swap(array, storeIndex, right);
+        return storeIndex;
     }
 
-    private static void swap(int[] nums, int a, int b) {
-        int tmp = nums[a];
-        nums[a] = nums[b];
-        nums[b] = tmp;
+    private static void swap(int[] array, int i, int j) {
+        int temp = array[i];
+        array[i] = array[j];
+        array[j] = temp;
     }
 }


Test patch:
diff --git a/src/test/java/com/thealgorithms/maths/FindKthNumberTest.java b/src/test/java/com/thealgorithms/maths/FindKthNumberTest.java
new file mode 100644
index 00000000..ddf62ff1
--- /dev/null
+++ b/src/test/java/com/thealgorithms/maths/FindKthNumberTest.java
@@ -0,0 +1,59 @@
+package com.thealgorithms.maths;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+
+import java.util.Arrays;
+import java.util.Random;
+import org.junit.jupiter.api.Test;
+
+public class FindKthNumberTest {
+    @Test
+    public void testFindKthMaxTypicalCases() {
+        int[] array1 = {3, 2, 1, 4, 5};
+        assertEquals(3, FindKthNumber.findKthMax(array1, 3));
+        assertEquals(4, FindKthNumber.findKthMax(array1, 2));
+        assertEquals(5, FindKthNumber.findKthMax(array1, 1));
+
+        int[] array2 = {7, 5, 8, 2, 1, 6};
+        assertEquals(5, FindKthNumber.findKthMax(array2, 4));
+        assertEquals(6, FindKthNumber.findKthMax(array2, 3));
+        assertEquals(8, FindKthNumber.findKthMax(array2, 1));
+    }
+
+    @Test
+    public void testFindKthMaxEdgeCases() {
+        int[] array1 = {1};
+        assertEquals(1, FindKthNumber.findKthMax(array1, 1));
+
+        int[] array2 = {5, 3};
+        assertEquals(5, FindKthNumber.findKthMax(array2, 1));
+        assertEquals(3, FindKthNumber.findKthMax(array2, 2));
+    }
+
+    @Test
+    public void testFindKthMaxInvalidK() {
+        int[] array = {1, 2, 3, 4, 5};
+        assertThrows(IllegalArgumentException.class, () -> FindKthNumber.findKthMax(array, 0));
+        assertThrows(IllegalArgumentException.class, () -> FindKthNumber.findKthMax(array, 6));
+    }
+
+    @Test
+    public void testFindKthMaxLargeArray() {
+        int[] array = generateArray(1000);
+        int k = new Random().nextInt(array.length);
+        int result = FindKthNumber.findKthMax(array, k);
+        Arrays.sort(array);
+        assertEquals(array[array.length - k], result);
+    }
+
+    public static int[] generateArray(int capacity) {
+        int size = new Random().nextInt(capacity) + 1;
+        int[] array = new int[size];
+
+        for (int i = 0; i < size; i++) {
+            array[i] = new Random().nextInt(100); // Ensure positive values for testing
+        }
+        return array;
+    }
+}