Merge pull request eugenp#5398 from moisko/master

lor6 · web-flow · commit d385e7bbf5ef · 2018-10-09T12:58:32.000+03:00
BAEL-2212: Insertion Sort in Java
diff --git a/algorithms/src/main/java/com/baeldung/algorithms/insertionsort/InsertionSort.java b/algorithms/src/main/java/com/baeldung/algorithms/insertionsort/InsertionSort.java
@@ -0,0 +1,41 @@
+package com.baeldung.algorithms.insertionsort;
+
+public class InsertionSort {
+
+    public static void insertionSortImperative(int[] input) {
+        for (int i = 1; i < input.length; i++) {
+            int key = input[i];
+            int j = i - 1;
+            while (j >= 0 && input[j] > key) {
+                input[j + 1] = input[j];
+                j = j - 1;
+            }
+            input[j + 1] = key;
+        }
+    }
+
+    public static void insertionSortRecursive(int[] input) {
+        insertionSortRecursive(input, input.length);
+    }
+
+    private static void insertionSortRecursive(int[] input, int i) {
+        // base case
+        if (i <= 1) {
+            return;
+        }
+
+        // sort the first i - 1 elements of the array
+        insertionSortRecursive(input, i - 1);
+
+        // then find the correct position of the element at position i
+        int key = input[i - 1];
+        int j = i - 2;
+        // shifting the elements from their position by 1
+        while (j >= 0 && input[j] > key) {
+            input[j + 1] = input[j];
+            j = j - 1;
+        }
+        // inserting the key at the appropriate position
+        input[j + 1] = key;
+    }
+}
diff --git a/algorithms/src/test/java/algorithms/insertionsort/InsertionSortUnitTest.java b/algorithms/src/test/java/algorithms/insertionsort/InsertionSortUnitTest.java
@@ -0,0 +1,26 @@
+package algorithms.insertionsort;
+
+import com.baeldung.algorithms.insertionsort.InsertionSort;
+import org.junit.Test;
+
+import static org.junit.Assert.assertArrayEquals;
+
+public class InsertionSortUnitTest {
+
+    @Test
+    public void givenUnsortedArray_whenInsertionSortImperatively_thenItIsSortedInAscendingOrder() {
+        int[] input = {6, 2, 3, 4, 5, 1};
+        InsertionSort.insertionSortImperative(input);
+        int[] expected = {1, 2, 3, 4, 5, 6};
+        assertArrayEquals("the two arrays are not equal", expected, input);
+    }
+
+    @Test
+    public void givenUnsortedArray_whenInsertionSortRecursively_thenItIsSortedInAscendingOrder() {
+        // int[] input = {6, 4, 5, 2, 3, 1};
+        int[] input = {6, 4};
+        InsertionSort.insertionSortRecursive(input);
+        int[] expected = {1, 2, 3, 4, 5, 6};
+        assertArrayEquals("the two arrays are not equal", expected, input);
+    }
+}
