refactor quick sort (#95)

realDuYuanChao · github-actions · web-flow · commit 56b6d169703f · 2021-04-06T16:47:42.000+08:00
* refactor quicksort

* Formatted with Google Java Formatter

Co-authored-by: github-actions &lt;${GITHUB_ACTOR}@users.noreply.github.com&gt;
diff --git a/src/main/java/com/examplehub/sorts/QuickSort.java b/src/main/java/com/examplehub/sorts/QuickSort.java
@@ -1,77 +1,75 @@
 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);
   }
 
+  private int partition(int[] number, int left, int right) {
+    int pivot = number[left];
+    while (left < right) {
+      while (left < right && number[right] >= pivot) {
+        right--;
+      }
+      number[left] = number[right];
+
+      while (left < right && number[left] <= pivot) {
+        left++;
+      }
+      number[right] = number[left];
+    }
+    number[left] = pivot;
+    return left;
+  }
+
   /**
    * 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--;
-      }
+    if (left < right) {
+      int pivotIndex = partition(numbers, left, right);
+      quickSort(numbers, left, pivotIndex - 1);
+      quickSort(numbers, pivotIndex + 1, right);
     }
-
-    SortUtils.swap(numbers, i, right);
-
-    quickSort(numbers, left, i - 1);
-    quickSort(numbers, i + 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);
   }
 
-  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 */
+  private static <T extends Comparable<T>> int partition(T[] array, int left, int right) {
+    T pivot = array[left];
+    while (left < right) {
+      while (left < right && array[right].compareTo(pivot) >= 0) {
+        right--;
       }
-      while (j >= 0 && array[j].compareTo(pivot) >= 0) {
-        j--; /* move j backward */
-      }
-      if (i < j) {
-        SortUtils.swap(array, i, j);
-        i++;
-        j--;
+      array[left] = array[right];
+
+      while (left < right && array[left].compareTo(pivot) <= 0) {
+        left++;
       }
+      array[right] = array[left];
     }
+    array[left] = pivot;
+    return left;
+  }
 
-    SortUtils.swap(array, i, right);
-
-    quickSort(array, left, i - 1);
-    quickSort(array, i + 1, right);
+  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);
+    }
   }
 }
