Repository: TheAlgorithms/Java
Pull request #3622 (2022-10-21 18:42:17)

Modify Insertion sort implementation to classical one + add function insertion-sentinel sort.
### **Describe your change:**
1. Current implementation of Insertion sort is not the classic one, which is described here - [wikipedia](https://en.wikipedia.org/wiki/Insertion_sort)
2. Add additional function `sentinelSort` which is the modification of classical implementation, faster one. 
3. Add isSorted function to SortUtils class.
4. Add SortUtilsRandomGenerator class to be able to generate random values and arrays. (It could be extended with additional functions)
5. Add unit tests.


- [x] Add an algorithm?
- [x] Fix a bug or typo in an existing algorithm?
- [ ] Documentation change?

#### References

<!-- Add any reference to previous pull-request or issue -->

### **Checklist:**

<!-- Remove items that do not apply. 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.
- [x] I know that pull requests will not be merged if they fail the automated tests.
- [x] This PR only changes one algorithm file. To ease review, please open separate PRs for separate algorithms.
- [x] All new Java files are placed inside an existing directory.
- [x] All filenames are in all uppercase characters with no spaces or dashes.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in its comments that points to Wikipedia or other similar explanation.
- [x] If this pull request resolves one or more open issues then the commit message contains `Fixes: #{$ISSUE_NO}`.



Patch:
diff --git a/src/main/java/com/thealgorithms/sorts/InsertionSort.java b/src/main/java/com/thealgorithms/sorts/InsertionSort.java
index 9fec4d40..594379a5 100644
--- a/src/main/java/com/thealgorithms/sorts/InsertionSort.java
+++ b/src/main/java/com/thealgorithms/sorts/InsertionSort.java
@@ -1,7 +1,8 @@
 package com.thealgorithms.sorts;
 
-import static com.thealgorithms.sorts.SortUtils.less;
-import static com.thealgorithms.sorts.SortUtils.print;
+import java.util.function.Function;
+
+import static com.thealgorithms.sorts.SortUtils.*;
 
 class InsertionSort implements SortAlgorithm {
 
@@ -9,21 +10,51 @@ class InsertionSort implements SortAlgorithm {
      * Generic insertion sort algorithm in increasing order.
      *
      * @param array the array to be sorted.
-     * @param <T> the class of array.
+     * @param <T>   the class of array.
      * @return sorted array.
      */
     @Override
     public <T extends Comparable<T>> T[] sort(T[] array) {
-        for (int i = 1; i < array.length; i++) {
-            T insertValue = array[i];
-            int j;
-            for (j = i - 1; j >= 0 && less(insertValue, array[j]); j--) {
-                array[j + 1] = array[j];
-            }
-            if (j != i - 1) {
-                array[j + 1] = insertValue;
+        for (int i = 1; i < array.length; i++)
+            for (int j = i; j > 0 && less(array[j], array[j - 1]); j--)
+                swap(array, j, j - 1);
+        return array;
+    }
+
+    /**
+     * Sentinel sort is a function which on the first step finds the minimal element in the provided
+     * array and puts it to the zero position, such a trick gives us an ability to avoid redundant
+     * comparisons like `j > 0` and swaps (we can move elements on position right, until we find
+     * the right position for the chosen element) on further step.
+     *
+     * @param array the array to be sorted
+     * @param <T>   Generic type which extends Comparable interface.
+     * @return sorted array
+     */
+    public <T extends Comparable<T>> T[] sentinelSort(T[] array) {
+        int minElemIndex = 0;
+        int n = array.length;
+        if (n < 1)
+            return array;
+
+        // put the smallest element to the 0 position as a sentinel, which will allow us to avoid
+        // redundant comparisons like `j > 0` further
+        for (int i = 1; i < n; i++)
+            if (less(array[i], array[minElemIndex]))
+                minElemIndex = i;
+        swap(array, 0, minElemIndex);
+
+        for (int i = 2; i < n; i++) {
+            int j = i;
+            T currentValue = array[i];
+            while (less(currentValue, array[j - 1])) {
+                array[j] = array[j - 1];
+                j--;
             }
+
+            array[j] = currentValue;
         }
+
         return array;
     }
 
@@ -31,15 +62,27 @@ class InsertionSort implements SortAlgorithm {
      * Driver Code
      */
     public static void main(String[] args) {
-        Integer[] integers = { 4, 23, 6, 78, 1, 54, 231, 9, 12 };
-        InsertionSort sort = new InsertionSort();
-        sort.sort(integers);
-        print(integers);
-        /* [1, 4, 6, 9, 12, 23, 54, 78, 231] */
-
-        String[] strings = { "c", "a", "e", "b", "d" };
-        sort.sort(strings);
-        print(strings);
-        /* [a, b, c, d, e] */
+        int size = 100_000;
+        Double[] randomArray = SortUtilsRandomGenerator.generateArray(size);
+        Double[] copyRandomArray = new Double[size];
+        System.arraycopy(randomArray, 0, copyRandomArray, 0, size);
+
+        InsertionSort insertionSort = new InsertionSort();
+        double insertionTime = measureApproxExecTime(insertionSort::sort, randomArray);
+        System.out.printf("Original insertion time: %5.2f  sec.\n", insertionTime);
+
+        double insertionSentinelTime = measureApproxExecTime(insertionSort::sentinelSort, copyRandomArray);
+        System.out.printf("Sentinel insertion time: %5.2f  sec.\n", insertionSentinelTime);
+
+        // ~ 1.5 time sentinel sort is faster, then classical Insertion sort implementation.
+        System.out.printf("Sentinel insertion is %f3.2 time faster than Original insertion sort\n",
+                insertionTime / insertionSentinelTime);
+    }
+
+    private static double measureApproxExecTime(Function<Double[], Double[]> sortAlgorithm, Double[] randomArray) {
+        long start = System.currentTimeMillis();
+        sortAlgorithm.apply(randomArray);
+        long end = System.currentTimeMillis();
+        return (end - start) / 1000.0;
     }
 }
diff --git a/src/main/java/com/thealgorithms/sorts/SortUtils.java b/src/main/java/com/thealgorithms/sorts/SortUtils.java
index 27774103..83b94c9a 100644
--- a/src/main/java/com/thealgorithms/sorts/SortUtils.java
+++ b/src/main/java/com/thealgorithms/sorts/SortUtils.java
@@ -99,4 +99,17 @@ final class SortUtils {
             swap(array, left++, right--);
         }
     }
+
+    /**
+     * Function to check if the array is sorted. By default, it will check if the array is sorted in ASC order.
+     *
+     * @param array - an array which to check is it sorted or not.
+     * @return true - if array sorted in ASC order, false otherwise.
+     */
+    static <T extends Comparable<T>> boolean isSorted(T[] array) {
+        for (int i = 1; i < array.length; i++)
+            if (less(array[i], array[i - 1]))
+                return false;
+        return true;
+    }
 }
diff --git a/src/main/java/com/thealgorithms/sorts/SortUtilsRandomGenerator.java b/src/main/java/com/thealgorithms/sorts/SortUtilsRandomGenerator.java
new file mode 100644
index 00000000..aad511c7
--- /dev/null
+++ b/src/main/java/com/thealgorithms/sorts/SortUtilsRandomGenerator.java
@@ -0,0 +1,38 @@
+package com.thealgorithms.sorts;
+
+import java.util.Random;
+
+public class SortUtilsRandomGenerator {
+
+    private static final Random random;
+    private static final long seed;
+
+    static {
+        seed = System.currentTimeMillis();
+        random = new Random(seed);
+    }
+
+
+    /**
+     * Function to generate array of double values, with predefined size.
+     *
+     * @param size result array size
+     * @return array of Double values, randomly generated, each element is between [0, 1)
+     */
+    public static Double[] generateArray(int size) {
+        Double[] arr = new Double[size];
+        for (int i = 0; i < size; i++)
+            arr[i] = generateDouble();
+        return arr;
+    }
+
+    /**
+     * Function to generate Double value.
+     *
+     * @return Double value [0, 1)
+     */
+    public static Double generateDouble() {
+        return random.nextDouble();
+    }
+
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/sorts/InsertionSortTest.java b/src/test/java/com/thealgorithms/sorts/InsertionSortTest.java
new file mode 100644
index 00000000..280b512e
--- /dev/null
+++ b/src/test/java/com/thealgorithms/sorts/InsertionSortTest.java
@@ -0,0 +1,114 @@
+package com.thealgorithms.sorts;
+
+import org.junit.jupiter.api.BeforeEach;
+import org.junit.jupiter.api.Test;
+
+import java.util.function.Function;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+class InsertionSortTest {
+    private InsertionSort insertionSort;
+
+    @BeforeEach
+    void setUp() {
+        insertionSort = new InsertionSort();
+    }
+
+    @Test
+    void insertionSortSortEmptyArrayShouldPass() {
+        testEmptyArray(insertionSort::sort);
+        testEmptyArray(insertionSort::sentinelSort);
+    }
+
+    private void testEmptyArray(Function<Integer[], Integer[]> sortAlgorithm) {
+        Integer[] array = {};
+        Integer[] sorted = sortAlgorithm.apply(array);
+        Integer[] expected = {};
+        assertArrayEquals(expected, sorted);
+        assertTrue(SortUtils.isSorted(sorted));
+    }
+
+    @Test
+    void insertionSortClassicalSortSingleValueArrayShouldPass() {
+        testSingleValue(insertionSort::sort);
+        testSingleValue(insertionSort::sentinelSort);
+    }
+
+    private void testSingleValue(Function<Integer[], Integer[]> sortAlgorithm) {
+        Integer[] array = {7};
+        Integer[] sorted = sortAlgorithm.apply(array);
+        Integer[] expected = {7};
+        assertArrayEquals(expected, sorted);
+        assertTrue(SortUtils.isSorted(sorted));
+    }
+
+    @Test
+    void insertionSortClassicalWithIntegerArrayShouldPass() {
+        testIntegerArray(insertionSort::sort);
+        testIntegerArray(insertionSort::sentinelSort);
+    }
+
+    private void testIntegerArray(Function<Integer[], Integer[]> sortAlgorithm) {
+        Integer[] array = {49, 4, 36, 9, 144, 1};
+        Integer[] sorted = sortAlgorithm.apply(array);
+        Integer[] expected = {1, 4, 9, 36, 49, 144};
+        assertArrayEquals(expected, sorted);
+        assertTrue(SortUtils.isSorted(sorted));
+    }
+
+    @Test
+    void insertionSortClassicalForArrayWithNegativeValuesShouldPass() {
+        testWithNegativeValues(insertionSort::sort);
+        testWithNegativeValues(insertionSort::sentinelSort);
+    }
+
+    private void testWithNegativeValues(Function<Integer[], Integer[]> sortAlgorithm) {
+        Integer[] array = {49, -36, -144, -49, 1, 9};
+        Integer[] sorted = sortAlgorithm.apply(array);
+        Integer[] expected = {-144, -49, -36, 1, 9, 49};
+        assertArrayEquals(expected, sorted);
+        assertTrue(SortUtils.isSorted(sorted));
+    }
+
+    @Test
+    void insertionSortClassicalForArrayWithDuplicateValuesShouldPass() {
+        testWithDuplicates(insertionSort::sort);
+        testWithDuplicates(insertionSort::sentinelSort);
+    }
+
+    private void testWithDuplicates(Function<Integer[], Integer[]> sortAlgorithm) {
+        Integer[] array = {36, 1, 49, 1, 4, 9};
+        Integer[] sorted = sortAlgorithm.apply(array);
+        Integer[] expected = {1, 1, 4, 9, 36, 49};
+        assertArrayEquals(expected, sorted);
+        assertTrue(SortUtils.isSorted(sorted));
+    }
+
+    @Test
+    void insertionSortClassicalWithStringArrayShouldPass() {
+        testWithStringArray(insertionSort::sort);
+        testWithStringArray(insertionSort::sentinelSort);
+    }
+
+    private void testWithStringArray(Function<String[], String[]> sortAlgorithm) {
+        String[] array = {"c", "a", "e", "b", "d"};
+        String[] sorted = sortAlgorithm.apply(array);
+        String[] expected = {"a", "b", "c", "d", "e"};
+        assertArrayEquals(expected, sorted);
+        assertTrue(SortUtils.isSorted(sorted));
+    }
+
+    @Test
+    void insertionSortClassicalWithRandomArrayPass() {
+        testWithRandomArray(insertionSort::sort);
+        testWithRandomArray(insertionSort::sentinelSort);
+    }
+
+    private void testWithRandomArray(Function<Double[], Double[]> sortAlgorithm) {
+        int randomSize = (int) (SortUtilsRandomGenerator.generateDouble() * 10_000);
+        Double[] array = SortUtilsRandomGenerator.generateArray(randomSize);
+        Double[] sorted = sortAlgorithm.apply(array);
+        assertTrue(SortUtils.isSorted(sorted));
+    }
+}
diff --git a/src/test/java/com/thealgorithms/sorts/SortUtilsRandomGeneratorTest.java b/src/test/java/com/thealgorithms/sorts/SortUtilsRandomGeneratorTest.java
new file mode 100644
index 00000000..30fd22c2
--- /dev/null
+++ b/src/test/java/com/thealgorithms/sorts/SortUtilsRandomGeneratorTest.java
@@ -0,0 +1,31 @@
+package com.thealgorithms.sorts;
+
+import org.junit.jupiter.api.RepeatedTest;
+import org.junit.jupiter.api.Test;
+
+import static org.assertj.core.api.Assertions.assertThat;
+
+class SortUtilsRandomGeneratorTest {
+
+    @RepeatedTest(1000)
+    void generateArray() {
+        int size = 1_000;
+        Double[] doubles = SortUtilsRandomGenerator.generateArray(size);
+        assertThat(doubles).hasSize(size);
+        assertThat(doubles).doesNotContainNull();
+    }
+
+    @Test
+    void generateArrayEmpty() {
+        int size = 0;
+        Double[] doubles = SortUtilsRandomGenerator.generateArray(size);
+        assertThat(doubles).hasSize(size);
+    }
+
+    @RepeatedTest(1000)
+    void generateDouble() {
+        Double randomDouble = SortUtilsRandomGenerator.generateDouble();
+        assertThat(randomDouble).isBetween(0.0, 1.0);
+        assertThat(randomDouble).isNotEqualTo(1.0);
+    }
+}
diff --git a/src/test/java/com/thealgorithms/sorts/SortUtilsTest.java b/src/test/java/com/thealgorithms/sorts/SortUtilsTest.java
new file mode 100644
index 00000000..bb558727
--- /dev/null
+++ b/src/test/java/com/thealgorithms/sorts/SortUtilsTest.java
@@ -0,0 +1,44 @@
+package com.thealgorithms.sorts;
+
+import org.junit.jupiter.api.Test;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+class SortUtilsTest {
+
+    @Test
+    void isSortedEmptyArray() {
+        Double[] emptyArray = {};
+        assertTrue(SortUtils.isSorted(emptyArray));
+    }
+
+    @Test
+    void isSortedWithSingleElement() {
+        Double[] singleElementArray = {1.0};
+        assertTrue(SortUtils.isSorted(singleElementArray));
+    }
+
+    @Test
+    void isSortedTrue() {
+        Integer[] array = {1, 1, 2, 3, 5, 8, 11};
+        assertTrue(SortUtils.isSorted(array));
+
+        Integer[] identicalArray = {1, 1, 1, 1, 1};
+        assertTrue(SortUtils.isSorted(identicalArray));
+
+        Double[] doubles = {-15.123, -15.111, 0.0, 0.12, 0.15};
+        assertTrue(SortUtils.isSorted(doubles));
+    }
+
+    @Test
+    void isSortedFalse() {
+        Double[] array = {1.0, 3.0, -0.15};
+        assertFalse(SortUtils.isSorted(array));
+
+        Integer[] array2 = {14, 15, 16, 1};
+        assertFalse(SortUtils.isSorted(array2));
+
+        Integer[] array3 = {5, 4, 3, 2, 1};
+        assertFalse(SortUtils.isSorted(array3));
+    }
+}