Repository: TheAlgorithms/Java
Pull request #3887 (2023-02-18 06:48:17)

Add Introspective Search - Assigned to Me
<!-- 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.



Patch:
diff --git a/src/main/java/com/thealgorithms/sorts/IntrospectiveSort.java b/src/main/java/com/thealgorithms/sorts/IntrospectiveSort.java
new file mode 100644
index 00000000..930bb02c
--- /dev/null
+++ b/src/main/java/com/thealgorithms/sorts/IntrospectiveSort.java
@@ -0,0 +1,90 @@
+package com.thealgorithms.sorts;
+
+/**
+ * Introspective Sort Algorithm Implementation
+ *
+ * @see <a href="https://en.wikipedia.org/wiki/Introsort">IntroSort Algorithm</a>
+ */
+public class IntrospectiveSort implements SortAlgorithm {
+
+    private static final int INSERTION_SORT_THRESHOLD = 16;
+
+    @Override
+    public <T extends Comparable<T>> T[] sort(T[] a) {
+        int n = a.length;
+        introSort(a, 0, n - 1, 2 * (int) (Math.log(n) / Math.log(2)));
+        return a;
+    }
+
+    private static <T extends Comparable<T>> void swap(T[] a, int i, int j) {
+        T temp = a[i];
+        a[i] = a[j];
+        a[j] = temp;
+    }
+
+    private static <T extends Comparable<T>> void introSort(T[] a, int low, int high, int depth) {
+        while (high - low > INSERTION_SORT_THRESHOLD) {
+            if (depth == 0) {
+                heapSort(a, low, high);
+                return;
+            }
+            int pivotIndex = partition(a, low, high);
+            introSort(a, pivotIndex + 1, high, depth - 1);
+            high = pivotIndex - 1;
+        }
+        insertionSort(a, low, high);
+    }
+
+    private static <T extends Comparable<T>> int partition(T[] a, int low, int high) {
+        int pivotIndex = low + (int) (Math.random() * (high - low + 1));
+        swap(a, pivotIndex, high);
+        T pivot = a[high];
+        int i = low - 1;
+        for (int j = low; j <= high - 1; j++) {
+            if (a[j].compareTo(pivot) <= 0) {
+                i++;
+                swap(a, i, j);
+            }
+        }
+        swap(a, i + 1, high);
+        return i + 1;
+    }
+
+    private static <T extends Comparable<T>> void insertionSort(T[] a, int low, int high) {
+        for (int i = low + 1; i <= high; i++) {
+            T key = a[i];
+            int j = i - 1;
+            while (j >= low && a[j].compareTo(key) > 0) {
+                a[j + 1] = a[j];
+                j--;
+            }
+            a[j + 1] = key;
+        }
+    }
+
+    private static <T extends Comparable<T>> void heapSort(T[] a, int low, int high) {
+        for (int i = (high + low - 1) / 2; i >= low; i--) {
+            heapify(a, i, high - low + 1, low);
+        }
+        for (int i = high; i > low; i--) {
+            swap(a, low, i);
+            heapify(a, low, i - low, low);
+        }
+    }
+
+    private static <T extends Comparable<T>> void heapify(T[] a, int i, int n, int low) {
+        int left = 2 * i - low + 1;
+        int right = 2 * i - low + 2;
+        int largest = i;
+        if (left < n && a[left].compareTo(a[largest]) > 0) {
+            largest = left;
+        }
+        if (right < n && a[right].compareTo(a[largest]) > 0) {
+            largest = right;
+        }
+        if (largest != i) {
+            swap(a, i, largest);
+            heapify(a, largest, n, low);
+        }
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/sorts/IntrospectiveSortTest.java b/src/test/java/com/thealgorithms/sorts/IntrospectiveSortTest.java
new file mode 100644
index 00000000..caaf3f4b
--- /dev/null
+++ b/src/test/java/com/thealgorithms/sorts/IntrospectiveSortTest.java
@@ -0,0 +1,65 @@
+package com.thealgorithms.sorts;
+
+import org.junit.jupiter.api.Test;
+
+import static org.junit.jupiter.api.Assertions.assertArrayEquals;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+
+public class IntrospectiveSortTest {
+    @Test
+    // valid test case
+    public void StrandSortNonDuplicateTest() {
+        Integer[] expectedArray = {1, 2, 3, 4, 5};
+        Integer[] actualList = new IntrospectiveSort().sort(expectedArray);
+        assertArrayEquals(expectedArray, actualList);
+    }
+
+    @Test
+    // valid test case
+    public void StrandSortDuplicateTest() {
+        Integer[] expectedArray = {2, 2, 2, 5, 7};
+        Integer[] actualList = new IntrospectiveSort().sort(expectedArray);
+        assertArrayEquals(expectedArray, actualList);
+    }
+
+    @Test
+    // valid test case
+    public void StrandSortEmptyTest() {
+        Integer[] expectedArray = {};
+        Integer[] actualList = new IntrospectiveSort().sort(expectedArray);
+        assertArrayEquals(expectedArray, actualList);
+    }
+
+    @Test
+    // valid test case
+    public void StrandSortNullTest() {
+        Integer[] expectedArray = null;
+        assertThrows(NullPointerException.class, () -> {
+            new IntrospectiveSort().sort(expectedArray);
+        });
+    }
+
+    @Test
+    // valid test case
+    public void StrandSortNegativeTest() {
+        Integer[] expectedArray = {-1, -2, -3, -4, -5};
+        Integer[] actualList = new IntrospectiveSort().sort(expectedArray);
+        assertArrayEquals(expectedArray, actualList);
+    }
+
+    @Test
+    // valid test case
+    public void StrandSortNegativeAndPositiveTest() {
+        Integer[] expectedArray = {-1, -2, -3, 4, 5};
+        Integer[] actualList = new IntrospectiveSort().sort(expectedArray);
+        assertArrayEquals(expectedArray, actualList);
+    }
+
+    @Test
+    // valid test case
+    public void allSameTest() {
+        Integer[] expectedArray = {1, 1, 1, 1, 1};
+        Integer[] actualList = new IntrospectiveSort().sort(expectedArray);
+        assertArrayEquals(expectedArray, actualList);
+    }
+}