Added Sort Interface

realDuYuanChao · realDuYuanChao · commit 67336ce1d319 · 2020-09-27T23:04:14.000+08:00
Added InsertionSort
diff --git a/src/main/java/com/examplehub/sorts/BubbleSort.java b/src/main/java/com/examplehub/sorts/BubbleSort.java
@@ -1,13 +1,13 @@
 package com.examplehub.sorts;
 
-public class BubbleSort {
+public class BubbleSort implements Sort {
 
     /**
      * BubbleSort algorithm implements.
      *
      * @param numbers the numbers to be sorted.
      */
-    public static void sort(int[] numbers) {
+    public void sort(int[] numbers) {
         for (int i = 0; i < numbers.length - 1; ++i) {
             boolean swapped = false;
             for (int j = 0; j < numbers.length - 1 - i; ++j) {
@@ -28,9 +28,9 @@ public static void sort(int[] numbers) {
      * Generic BubbleSort algorithm implements.
      *
      * @param array the array to be sorted.
-     * @param <T>   the class of the objects in the array.
+     * @param <T>   the class of the objects in the list.
      */
-    public static <T extends Comparable<T>> void sort(T[] array) {
+    public <T extends Comparable<T>> void sort(T[] array) {
         for (int i = 0; i < array.length - 1; ++i) {
             boolean swapped = false;
             for (int j = 0; j < array.length - 1 - i; ++j) {
diff --git a/src/main/java/com/examplehub/sorts/InsertionSort.java b/src/main/java/com/examplehub/sorts/InsertionSort.java
@@ -0,0 +1,41 @@
+package com.examplehub.sorts;
+
+public class InsertionSort implements Sort {
+
+    /**
+     * InsertionSort algorithm implements.
+     *
+     * @param numbers the numbers to be sorted.
+     */
+    public void sort(int[] numbers) {
+        for (int i = 1; i < numbers.length; ++i) {
+            int j = i - 1;
+            int key = numbers[i];
+            while (j >= 0 && key < numbers[j]) {
+                numbers[j + 1] = numbers[j];
+                --j;
+            }
+            if (j != i - 1) {
+                numbers[j + 1] = key;
+            }
+        }
+    }
+
+    /**
+     * Generic InsertionSort algorithm implements.
+     *
+     * @param array the array to be sorted.
+     * @param <T>   the class of the objects in the list.
+     */
+    public <T extends Comparable<T>> void sort(T[] array) {
+        for (int i = 1; i < array.length; ++i) {
+            int j = i - 1;
+            T key = array[i];
+            while (j >= 0 && key.compareTo(array[j]) < 0) {
+                array[j + 1] = array[j];
+                --j;
+            }
+            array[j + 1] = key;
+        }
+    }
+}
diff --git a/src/main/java/com/examplehub/sorts/Sort.java b/src/main/java/com/examplehub/sorts/Sort.java
@@ -0,0 +1,7 @@
+package com.examplehub.sorts;
+
+public interface Sort {
+    void sort(int[] numbers);
+
+    <T extends Comparable<T>> void sort(T[] array);
+}
diff --git a/src/test/java/com/examplehub/sorts/BubbleSortTest.java b/src/test/java/com/examplehub/sorts/BubbleSortTest.java
@@ -2,6 +2,7 @@
 
 import com.examplehub.utils.RandomUtils;
 import com.examplehub.utils.SortUtils;
+import org.junit.jupiter.api.BeforeEach;
 import org.junit.jupiter.api.Test;
 
 import java.util.Arrays;
@@ -10,19 +11,25 @@
 
 class BubbleSortTest {
 
+    private Sort sort;
+
+    @BeforeEach
+    public void before() {
+        sort = new BubbleSort();
+    }
+
     @Test
     void testSort() {
         int[] ints = RandomUtils.randomInts(-50, 50, 100);
-        BubbleSort.sort(ints);
+        sort.sort(ints);
         assertTrue(SortUtils.isSorted(ints));
     }
 
     @Test
     void testSortIntegers() {
-
         Integer[] integers = Arrays.stream(RandomUtils.randomInts(-50, 50, 100))
                 .boxed().toArray(Integer[]::new);
-        BubbleSort.sort(integers);
+        sort.sort(integers);
         assertTrue(SortUtils.isSorted(integers));
     }
 
@@ -33,7 +40,7 @@ void testSortedDoubles() {
         for (int i = 0; i < doubles.length; ++i) {
             doubles[i] = tempDoubles[i];
         }
-        BubbleSort.sort(doubles);
+        sort.sort(doubles);
         assertTrue(SortUtils.isSorted(doubles));
     }
 }
diff --git a/src/test/java/com/examplehub/sorts/InsertionSortTest.java b/src/test/java/com/examplehub/sorts/InsertionSortTest.java
@@ -0,0 +1,46 @@
+package com.examplehub.sorts;
+
+import com.examplehub.utils.RandomUtils;
+import com.examplehub.utils.SortUtils;
+import org.junit.jupiter.api.BeforeEach;
+import org.junit.jupiter.api.Test;
+
+import java.util.Arrays;
+
+import static org.junit.jupiter.api.Assertions.assertTrue;
+
+class InsertionSortTest {
+
+    private Sort sort;
+
+    @BeforeEach
+    public void before() {
+        sort = new InsertionSort();
+    }
+
+    @Test
+    void sort() {
+        int[] ints = RandomUtils.randomInts(-50, 50, 100);
+        sort.sort(ints);
+        assertTrue(SortUtils.isSorted(ints));
+    }
+
+    @Test
+    void sortInteger() {
+        Integer[] integers = Arrays.stream(RandomUtils.randomInts(-50, 50, 100))
+                .boxed().toArray(Integer[]::new);
+        sort.sort(integers);
+        assertTrue(SortUtils.isSorted(integers));
+    }
+
+    @Test
+    void sortDouble() {
+        Double[] doubles = new Double[100];
+        double[] tempDoubles = RandomUtils.randomDoubles(-50, 50, 100);
+        for (int i = 0; i < doubles.length; ++i) {
+            doubles[i] = tempDoubles[i];
+        }
+        sort.sort(doubles);
+        assertTrue(SortUtils.isSorted(doubles));
+    }
+}
