Repository: TheAlgorithms/Java
Pull request #5239 (2024-06-18 21:10:33)

Refactoring BinaryInsertionSort according to common SortAlgorithm approach
Generify and refactor the BinaryInsertionSort class to align with the standard SortAlgorithm approach

<!--
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`


Patch:
diff --git a/src/main/java/com/thealgorithms/sorts/BinaryInsertionSort.java b/src/main/java/com/thealgorithms/sorts/BinaryInsertionSort.java
index 13076c61..b6f5d92e 100644
--- a/src/main/java/com/thealgorithms/sorts/BinaryInsertionSort.java
+++ b/src/main/java/com/thealgorithms/sorts/BinaryInsertionSort.java
@@ -1,17 +1,28 @@
 package com.thealgorithms.sorts;
 
-public class BinaryInsertionSort {
+/**
+ * BinaryInsertionSort class implements the SortAlgorithm interface using the binary insertion sort technique.
+ * Binary Insertion Sort improves upon the simple insertion sort by using binary search to find the appropriate
+ * location to insert the new element, reducing the number of comparisons in the insertion step.
+ */
+public class BinaryInsertionSort implements SortAlgorithm {
 
-    // Binary Insertion Sort method
-    public int[] binaryInsertSort(int[] array) {
+    /**
+     * Sorts the given array using the Binary Insertion 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
+     */
+    public <T extends Comparable<T>> T[] sort(T[] array) {
         for (int i = 1; i < array.length; i++) {
-            int temp = array[i];
+            final T temp = array[i];
             int low = 0;
             int high = i - 1;
 
             while (low <= high) {
                 final int mid = (low + high) >>> 1;
-                if (temp < array[mid]) {
+                if (temp.compareTo(array[mid]) < 0) {
                     high = mid - 1;
                 } else {
                     low = mid + 1;


Test patch:
diff --git a/src/test/java/com/thealgorithms/sorts/BinaryInsertionSortTest.java b/src/test/java/com/thealgorithms/sorts/BinaryInsertionSortTest.java
index bdd07029..82cb3ba6 100644
--- a/src/test/java/com/thealgorithms/sorts/BinaryInsertionSortTest.java
+++ b/src/test/java/com/thealgorithms/sorts/BinaryInsertionSortTest.java
@@ -1,27 +1,10 @@
 package com.thealgorithms.sorts;
 
-import static org.junit.jupiter.api.Assertions.assertArrayEquals;
+class BinaryInsertionSortTest extends SortingAlgorithmTest {
+    private final BinaryInsertionSort binaryInsertionSort = new BinaryInsertionSort();
 
-import org.junit.jupiter.api.Test;
-
-class BinaryInsertionSortTest {
-
-    BinaryInsertionSort bis = new BinaryInsertionSort();
-
-    @Test
-    // valid test case
-    public void binaryInsertionSortTestNonDuplicate() {
-        int[] array = {1, 0, 2, 5, 3, 4, 9, 8, 10, 6, 7};
-        int[] expResult = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
-        int[] actResult = bis.binaryInsertSort(array);
-        assertArrayEquals(expResult, actResult);
-    }
-
-    @Test
-    public void binaryInsertionSortTestDuplicate() {
-        int[] array = {1, 1, 1, 5, 9, 8, 7, 2, 6};
-        int[] expResult = {1, 1, 1, 2, 5, 6, 7, 8, 9};
-        int[] actResult = bis.binaryInsertSort(array);
-        assertArrayEquals(expResult, actResult);
+    @Override
+    SortAlgorithm getSortAlgorithm() {
+        return binaryInsertionSort;
     }
 }