Repository: TheAlgorithms/Java
Pull request #5314 (2024-08-10 08:14:03)

refactor: cleanup `BucketSort` 
### Refactoring of BucketSort

Several improvements have been made:

1. **Comment Refinement**: Redundant comments were removed, and relevant descriptions were moved directly into method-level documentation.

2. **Main Method Removal**: The `main` method was removed as it was redundant. Testing can be effectively handled through the provided unit tests, or by writing a simple test case if needed.

3. **Additional Unit Tests**: New unit tests were added.

4. **Stream API Usage**: During refactoring Java Streams were introduced to simplify and modernize the code.


<!--
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/5314?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 42.05%. 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 [(`0cd0ef2`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/0cd0ef2574596ab9b733451986b3c270b9b84da5?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).
> Report is 9 commits behind head on master.

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


```diff
@@             Coverage Diff              @@
##             master    #5314      +/-   ##
============================================
+ Coverage     41.47%   42.05%   +0.58%     
- Complexity     2556     2611      +55     
============================================
  Files           520      522       +2     
  Lines         15447    15550     +103     
  Branches       2947     2959      +12     
============================================
+ Hits           6406     6539     +133     
+ Misses         8747     8715      -32     
- Partials        294      296       +2     
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5314?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/sorts/BucketSort.java b/src/main/java/com/thealgorithms/sorts/BucketSort.java
index 2a48cca0..a6901ac3 100644
--- a/src/main/java/com/thealgorithms/sorts/BucketSort.java
+++ b/src/main/java/com/thealgorithms/sorts/BucketSort.java
@@ -3,117 +3,128 @@ package com.thealgorithms.sorts;
 import java.util.ArrayList;
 import java.util.Collections;
 import java.util.List;
-import java.util.Random;
 
 /**
- * Wikipedia: https://en.wikipedia.org/wiki/Bucket_sort
+ * BucketSort class provides a method to sort an array of elements using the Bucket Sort algorithm
+ * and implements the SortAlgorithm interface.
  */
-public final class BucketSort {
-    private BucketSort() {
-    }
+public class BucketSort implements SortAlgorithm {
 
-    public static void main(String[] args) {
-        int[] arr = new int[10];
+    // Constant that defines the divisor for determining the number of buckets
+    private static final int BUCKET_DIVISOR = 10;
 
-        /* generate 10 random numbers from -50 to 49 */
-        Random random = new Random();
-        for (int i = 0; i < arr.length; ++i) {
-            arr[i] = random.nextInt(100) - 50;
+    @Override
+    public <T extends Comparable<T>> T[] sort(T[] array) {
+        if (array.length == 0) {
+            return array;
         }
 
-        bucketSort(arr);
+        T min = findMin(array);
+        T max = findMax(array);
+        int numberOfBuckets = calculateNumberOfBuckets(array.length);
 
-        /* check array is sorted or not */
-        for (int i = 0, limit = arr.length - 1; i < limit; ++i) {
-            assert arr[i] <= arr[i + 1];
-        }
+        List<List<T>> buckets = initializeBuckets(numberOfBuckets);
+        distributeElementsIntoBuckets(array, buckets, min, max, numberOfBuckets);
+
+        return concatenateBuckets(buckets, array);
     }
 
     /**
-     * BucketSort algorithms implements
+     * Calculates the number of buckets to use based on the size of the array.
      *
-     * @param arr the array contains elements
+     * @param arrayLength the length of the array
+     * @return the number of buckets
      */
-    public static int[] bucketSort(int[] arr) {
-        /* get max value of arr */
-        int max = max(arr);
-
-        /* get min value of arr */
-        int min = min(arr);
-
-        /* number of buckets */
-        int numberOfBuckets = max - min + 1;
-
-        List<List<Integer>> buckets = new ArrayList<>(numberOfBuckets);
+    private int calculateNumberOfBuckets(final int arrayLength) {
+        return Math.max(arrayLength / BUCKET_DIVISOR, 1);
+    }
 
-        /* init buckets */
-        for (int i = 0; i < numberOfBuckets; ++i) {
+    /**
+     * Initializes a list of empty buckets.
+     *
+     * @param numberOfBuckets the number of buckets to initialize
+     * @param <T> the type of elements to be sorted
+     * @return a list of empty buckets
+     */
+    private <T extends Comparable<T>> List<List<T>> initializeBuckets(int numberOfBuckets) {
+        List<List<T>> buckets = new ArrayList<>(numberOfBuckets);
+        for (int i = 0; i < numberOfBuckets; i++) {
             buckets.add(new ArrayList<>());
         }
-
-        /* store elements to buckets */
-        for (int value : arr) {
-            int hash = hash(value, min, numberOfBuckets);
-            buckets.get(hash).add(value);
-        }
-
-        /* sort individual bucket */
-        for (List<Integer> bucket : buckets) {
-            Collections.sort(bucket);
-        }
-
-        /* concatenate buckets to origin array */
-        int index = 0;
-        for (List<Integer> bucket : buckets) {
-            for (int value : bucket) {
-                arr[index++] = value;
-            }
-        }
-
-        return arr;
+        return buckets;
     }
 
     /**
-     * Get index of bucket which of our elements gets placed into it.
+     * Distributes elements from the array into the appropriate buckets.
      *
-     * @param elem the element of array to be sorted
-     * @param min min value of array
-     * @param numberOfBucket the number of bucket
-     * @return index of bucket
+     * @param array the array of elements to distribute
+     * @param buckets the list of buckets
+     * @param min the minimum value in the array
+     * @param max the maximum value in the array
+     * @param numberOfBuckets the total number of buckets
+     * @param <T> the type of elements in the array
      */
-    private static int hash(int elem, int min, int numberOfBucket) {
-        return (elem - min) / numberOfBucket;
+    private <T extends Comparable<T>> void distributeElementsIntoBuckets(T[] array, List<List<T>> buckets, final T min, final T max, final int numberOfBuckets) {
+        for (final T element : array) {
+            int bucketIndex = hash(element, min, max, numberOfBuckets);
+            buckets.get(bucketIndex).add(element);
+        }
     }
 
     /**
-     * Calculate max value of array
+     * Concatenates the sorted buckets back into the original array.
      *
-     * @param arr the array contains elements
-     * @return max value of given array
+     * @param buckets the list of sorted buckets
+     * @param array the original array
+     * @param <T> the type of elements in the array
+     * @return the sorted array
      */
-    public static int max(int[] arr) {
-        int max = arr[0];
-        for (int value : arr) {
-            if (value > max) {
-                max = value;
+    private <T extends Comparable<T>> T[] concatenateBuckets(List<List<T>> buckets, T[] array) {
+        int index = 0;
+        for (List<T> bucket : buckets) {
+            Collections.sort(bucket);
+            for (T element : bucket) {
+                array[index++] = element;
             }
         }
-        return max;
+        return array;
     }
 
     /**
-     * Calculate min value of array
+     * The method computes the index of the bucket in which a given element should be placed.
+     * This is done by "normalizing" the element within the range of the array's minimum (min) and maximum (max) values,
+     * and then mapping this normalized value to a specific bucket index.
      *
-     * @param arr the array contains elements
-     * @return min value of given array
+     * @param element the element of the array
+     * @param min the minimum value in the array
+     * @param max the maximum value in the array
+     * @param numberOfBuckets the total number of buckets
+     * @param <T> the type of elements in the array
+     * @return the index of the bucket
      */
-    public static int min(int[] arr) {
-        int min = arr[0];
-        for (int value : arr) {
-            if (value < min) {
-                min = value;
+    private <T extends Comparable<T>> int hash(final T element, final T min, final T max, final int numberOfBuckets) {
+        double range = max.compareTo(min);
+        double normalizedValue = element.compareTo(min) / range;
+        return (int) (normalizedValue * (numberOfBuckets - 1));
+    }
+
+    private <T extends Comparable<T>> T findMin(T[] array) {
+        T min = array[0];
+        for (T element : array) {
+            if (element.compareTo(min) < 0) {
+                min = element;
             }
         }
         return min;
     }
+
+    private <T extends Comparable<T>> T findMax(T[] array) {
+        T max = array[0];
+        for (T element : array) {
+            if (element.compareTo(max) > 0) {
+                max = element;
+            }
+        }
+        return max;
+    }
 }


Test patch:
diff --git a/src/test/java/com/thealgorithms/sorts/BucketSortTest.java b/src/test/java/com/thealgorithms/sorts/BucketSortTest.java
index bd9d2e3d..a2dcb8ca 100644
--- a/src/test/java/com/thealgorithms/sorts/BucketSortTest.java
+++ b/src/test/java/com/thealgorithms/sorts/BucketSortTest.java
@@ -1,48 +1,8 @@
 package com.thealgorithms.sorts;
 
-import static org.junit.jupiter.api.Assertions.assertArrayEquals;
-
-import org.junit.jupiter.api.Test;
-
-public class BucketSortTest {
-
-    @Test
-    public void bucketSortSingleIntegerArray() {
-        int[] inputArray = {4};
-        int[] outputArray = BucketSort.bucketSort(inputArray);
-        int[] expectedOutput = {4};
-        assertArrayEquals(outputArray, expectedOutput);
-    }
-
-    @Test
-    public void bucketSortNonDuplicateIntegerArray() {
-        int[] inputArray = {6, 1, 99, 27, 15, 23, 36};
-        int[] outputArray = BucketSort.bucketSort(inputArray);
-        int[] expectedOutput = {1, 6, 15, 23, 27, 36, 99};
-        assertArrayEquals(outputArray, expectedOutput);
-    }
-
-    @Test
-    public void bucketSortDuplicateIntegerArray() {
-        int[] inputArray = {6, 1, 27, 15, 23, 27, 36, 23};
-        int[] outputArray = BucketSort.bucketSort(inputArray);
-        int[] expectedOutput = {1, 6, 15, 23, 23, 27, 27, 36};
-        assertArrayEquals(outputArray, expectedOutput);
-    }
-
-    @Test
-    public void bucketSortNonDuplicateIntegerArrayWithNegativeNum() {
-        int[] inputArray = {6, -1, 99, 27, -15, 23, -36};
-        int[] outputArray = BucketSort.bucketSort(inputArray);
-        int[] expectedOutput = {-36, -15, -1, 6, 23, 27, 99};
-        assertArrayEquals(outputArray, expectedOutput);
-    }
-
-    @Test
-    public void bucketSortDuplicateIntegerArrayWithNegativeNum() {
-        int[] inputArray = {6, -1, 27, -15, 23, 27, -36, 23};
-        int[] outputArray = BucketSort.bucketSort(inputArray);
-        int[] expectedOutput = {-36, -15, -1, 6, 23, 23, 27, 27};
-        assertArrayEquals(outputArray, expectedOutput);
+public class BucketSortTest extends SortingAlgorithmTest {
+    @Override
+    SortAlgorithm getSortAlgorithm() {
+        return new BucketSort();
     }
 }