add quick sort

realDuYuanChao · realDuYuanChao · commit fdbbb9addc43 · 2020-10-03T01:02:00.000+08:00
diff --git a/src/main/java/com/examplehub/sorts/QuickSort.java b/src/main/java/com/examplehub/sorts/QuickSort.java
@@ -0,0 +1,77 @@
+package com.examplehub.sorts;
+
+import com.examplehub.utils.SortUtils;
+
+public class QuickSort implements Sort {
+
+    @Override
+    public void sort(int[] numbers) {
+        quickSort(numbers, 0, numbers.length - 1);
+    }
+
+    /**
+     * QuickSort algorithm implements.
+     *
+     * @param numbers the numbers to be sorted.
+     */
+    public void quickSort(int[] numbers, int left, int right) {
+        if (left >= right) {
+            return;
+        }
+        int pivot = numbers[right]; /* pick last element as pivot */
+        /* begin partition */
+        int i = left; /* left pointer */
+        int j = right - 1; /* right pointer */
+        while (i <= j) {
+            while (numbers[i] < pivot) {
+                i++; /* move i forward */
+            }
+            while (j >= 0 && numbers[j] >= pivot) {
+                j--; /* move j backward */
+            }
+            if (i < j) {
+                SortUtils.swap(numbers, i, j);
+                i++;
+                j--;
+            }
+        }
+
+        SortUtils.swap(numbers, i, right);
+
+        quickSort(numbers, left, i - 1);
+        quickSort(numbers, i + 1, right);
+    }
+
+    @Override
+    public <T extends Comparable<T>> void sort(T[] array) {
+        quickSort(array, 0, array.length - 1);
+    }
+
+    public static <T extends Comparable<T>> void quickSort(T[] array, int left, int right) {
+        if (left >= right) {
+            return;
+        }
+        T pivot = array[right]; /* pick last element as pivot */
+        /* begin partition */
+        int i = left; /* left pointer */
+        int j = right - 1; /* right pointer */
+        while (i <= j) {
+            while (array[i].compareTo(pivot) < 0) {
+                i++; /* move i forward */
+            }
+            while (j >= 0 && array[j].compareTo(pivot) >= 0) {
+                j--; /* move j backward */
+            }
+            if (i < j) {
+                SortUtils.swap(array, i, j);
+                i++;
+                j--;
+            }
+        }
+
+        SortUtils.swap(array, i, right);
+
+        quickSort(array, left, i - 1);
+        quickSort(array, i + 1, right);
+    }
+}
diff --git a/src/main/java/com/examplehub/utils/SortUtils.java b/src/main/java/com/examplehub/utils/SortUtils.java
@@ -32,4 +32,31 @@ public static <T extends Comparable<T>> boolean isSorted(T[] array) {
         }
         return true;
     }
+
+    /**
+     * Swapped array elements at different index.
+     *
+     * @param numbers the numbers to be swapped.
+     * @param i       the first index.
+     * @param j       the second index.
+     */
+    public static void swap(int[] numbers, int i, int j) {
+        int temp = numbers[i];
+        numbers[i] = numbers[j];
+        numbers[j] = temp;
+    }
+
+    /**
+     * Generic swapped array elements at different index.
+     *
+     * @param numbers the numbers to be swapped.
+     * @param i       the first index.
+     * @param j       the second index.
+     * @param <T>     the class of the objects in the array.
+     */
+    public static <T extends Comparable<T>> void swap(T[] numbers, int i, int j) {
+        T temp = numbers[i];
+        numbers[i] = numbers[j];
+        numbers[j] = temp;
+    }
 }
diff --git a/src/test/java/com/examplehub/sorts/QuickSortTest.java b/src/test/java/com/examplehub/sorts/QuickSortTest.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.*;
+
+class QuickSortTest {
+
+    private Sort sort;
+
+    @BeforeEach
+    public void before() {
+        sort = new QuickSort();
+    }
+
+    @Test
+    void testQuickSort() {
+        int[] ints = RandomUtils.randomInts(-50, 50, 100);
+        sort.sort(ints);
+        assertTrue(SortUtils.isSorted(ints));
+    }
+
+    @Test
+    void testSortIntegers() {
+        Integer[] integers = Arrays.stream(RandomUtils.randomInts(-50, 50, 100))
+                .boxed().toArray(Integer[]::new);
+        sort.sort(integers);
+        assertTrue(SortUtils.isSorted(integers));
+    }
+
+    @Test
+    void testSortedDoubles() {
+        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));
+    }
+}
