update bubble sort (#187)

realDuYuanChao · web-flow · commit e2e83370fbd5 · 2021-10-06T20:51:35.000+08:00
update quick sort
diff --git a/src/main/java/com/examplehub/sorts/BubbleSortV2.java b/src/main/java/com/examplehub/sorts/BubbleSortV2.java
@@ -0,0 +1,45 @@
+package com.examplehub.sorts;
+
+import com.examplehub.utils.SortUtils;
+
+public class BubbleSortV2 implements Sort {
+
+  /**
+   * BubbleSort algorithm implements.
+   *
+   * @param numbers the numbers to be sorted.
+   */
+  public void sort(int[] numbers) {
+    int n = numbers.length - 1;
+    while (n != 0) {
+      int lastSwapIdx = 0;
+      for (int i = 0; i < n; ++i) {
+        if (numbers[i] > numbers[i + 1]) {
+          SortUtils.swap(numbers, i, i + 1);
+          lastSwapIdx = i;
+        }
+      }
+      n = lastSwapIdx;
+    }
+  }
+
+  /**
+   * Generic BubbleSort algorithm implements.
+   *
+   * @param array the array to be sorted.
+   * @param <T> the class of the objects in the array.
+   */
+  public <T extends Comparable<T>> void sort(T[] array) {
+    int n = array.length - 1;
+    while (n != 0) {
+      int lastSwapIdx = 0;
+      for (int i = 0; i < n; ++i) {
+        if (array[i].compareTo(array[i + 1]) > 0) {
+          SortUtils.swap(array, i, i + 1);
+          lastSwapIdx = i;
+        }
+      }
+      n = lastSwapIdx;
+    }
+  }
+}
diff --git a/src/main/java/com/examplehub/sorts/QuickSortLomutoPartition.java b/src/main/java/com/examplehub/sorts/QuickSortLomutoPartition.java
@@ -0,0 +1,67 @@
+package com.examplehub.sorts;
+
+import com.examplehub.utils.SortUtils;
+
+/**
+ * https://en.wikipedia.org/wiki/Quicksort#Lomuto_partition_scheme
+ */
+public class QuickSortLomutoPartition implements Sort {
+
+  @Override
+  public void sort(int[] numbers) {
+    quickSort(numbers, 0, numbers.length - 1);
+  }
+
+  private int partition(int[] number, int left, int right) {
+    int pivot = number[right];
+    for (int j = left; j < right; ++j) {
+      if (number[j] < pivot) {
+        SortUtils.swap(number, left++, j);
+      }
+    }
+    SortUtils.swap(number, left, right);
+    return left;
+  }
+  /**
+   * QuickSort algorithm implements.
+   *
+   * @param numbers the numbers to be sorted.
+   */
+  public void quickSort(int[] numbers, int left, int right) {
+    if (left < right) {
+      int pivotIndex = partition(numbers, left, right);
+      quickSort(numbers, left, pivotIndex - 1);
+      quickSort(numbers, pivotIndex + 1, right);
+    }
+  }
+
+  /**
+   * Generic quickSort algorithm implements.
+   *
+   * @param array the array to be sorted.
+   * @param <T> the class of the objects in the array.
+   */
+  @Override
+  public <T extends Comparable<T>> void sort(T[] array) {
+    quickSort(array, 0, array.length - 1);
+  }
+
+  private static <T extends Comparable<T>> int partition(T[] array, int left, int right) {
+    T pivot = array[right];
+    for (int j = left; j < right; j++) {
+      if (array[j].compareTo(pivot) < 0) {
+        SortUtils.swap(array, j, left++);
+      }
+    }
+    SortUtils.swap(array, left, right);
+    return left;
+  }
+
+  public static <T extends Comparable<T>> void quickSort(T[] array, int left, int right) {
+    if (left < right) {
+      int pivotIndex = partition(array, left, right);
+      quickSort(array, left, pivotIndex - 1);
+      quickSort(array, pivotIndex + 1, right);
+    }
+  }
+}
diff --git a/src/test/java/com/examplehub/sorts/BubbleSortV2Test.java b/src/test/java/com/examplehub/sorts/BubbleSortV2Test.java
@@ -0,0 +1,59 @@
+package com.examplehub.sorts;
+
+import com.examplehub.domain.Student;
+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 BubbleSortV2Test {
+
+  private Sort sort;
+
+  @BeforeEach
+  public void before() {
+    sort = new BubbleSortV2();
+  }
+
+  @Test
+  void testSort() {
+    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));
+  }
+
+  @Test
+  void testComparable() {
+    Student[] students = new Student[5];
+    students[0] = new Student(1, 98, 99, 100);
+    students[1] = new Student(2, 100, 99, 98);
+    students[2] = new Student(3, 100, 98, 99);
+    students[3] = new Student(4, 100, 100, 100);
+    students[4] = new Student(5, 99, 99, 99);
+    sort.sort(students);
+    assertTrue(SortUtils.isSorted(students));
+  }
+}
diff --git a/src/test/java/com/examplehub/sorts/QuickSortLomutoPartitionTest.java b/src/test/java/com/examplehub/sorts/QuickSortLomutoPartitionTest.java
@@ -0,0 +1,49 @@
+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 QuickSortLomutoPartitionTest {
+  private Sort sort;
+
+  @BeforeEach
+  public void before() {
+    sort = new QuickSortLomutoPartition();
+  }
+
+  @Test
+  void testQuickSort() {
+    int[] ints = RandomUtils.randomInts(-50, 50, 100);
+    sort.sort(ints);
+    assertTrue(SortUtils.isSorted(ints));
+
+    ints = new int[] {1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
+    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));
+  }
+}
