add sort utils (examplehub#142)

realDuYuanChao · github-actions · web-flow · commit c8d3c30d5435 · 2021-08-01T19:49:54.000+08:00
* add sort utils

* 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/BubbleSort.java b/src/main/java/com/examplehub/sorts/BubbleSort.java
@@ -1,5 +1,7 @@
 package com.examplehub.sorts;
 
+import com.examplehub.utils.SortUtils;
+
 public class BubbleSort implements Sort {
 
   /**
@@ -12,9 +14,7 @@ public void sort(int[] numbers) {
       boolean swapped = false;
       for (int j = 0; j < numbers.length - 1 - i; ++j) {
         if (numbers[j] > numbers[j + 1]) {
-          int temp = numbers[j];
-          numbers[j] = numbers[j + 1];
-          numbers[j + 1] = temp;
+          SortUtils.swap(numbers, j, j + 1);
           swapped = true;
         }
       }
@@ -35,9 +35,7 @@ public <T extends Comparable<T>> void sort(T[] array) {
       boolean swapped = false;
       for (int j = 0; j < array.length - 1 - i; ++j) {
         if (array[j].compareTo(array[j + 1]) > 0) {
-          T temp = array[j];
-          array[j] = array[j + 1];
-          array[j + 1] = temp;
+          SortUtils.swap(array, j, j + 1);
           swapped = true;
         }
       }
diff --git a/src/main/java/com/examplehub/sorts/BubbleSortRecursion.java b/src/main/java/com/examplehub/sorts/BubbleSortRecursion.java
@@ -1,5 +1,7 @@
 package com.examplehub.sorts;
 
+import com.examplehub.utils.SortUtils;
+
 public class BubbleSortRecursion implements Sort {
   @Override
   public void sort(int[] numbers) {
@@ -16,9 +18,7 @@ public void sortRecursion(int[] numbers, int length) {
     boolean swapped = false;
     for (int i = 0; i < length - 1; ++i) {
       if (numbers[i] > numbers[i + 1]) {
-        int temp = numbers[i];
-        numbers[i] = numbers[i + 1];
-        numbers[i + 1] = temp;
+        SortUtils.swap(numbers, i, i + 1);
         swapped = true;
       }
     }
@@ -43,9 +43,7 @@ public <T extends Comparable<T>> void sortRecursion(T[] array, int length) {
     boolean swapped = false;
     for (int i = 0; i < length - 1; ++i) {
       if (array[i].compareTo(array[i + 1]) > 0) {
-        T temp = array[i];
-        array[i] = array[i + 1];
-        array[i + 1] = temp;
+        SortUtils.swap(array, i, i + 1);
         swapped = true;
       }
     }
diff --git a/src/main/java/com/examplehub/sorts/QuickSort.java b/src/main/java/com/examplehub/sorts/QuickSort.java
@@ -1,5 +1,7 @@
 package com.examplehub.sorts;
 
+import com.examplehub.utils.SortUtils;
+
 public class QuickSort implements Sort {
 
   @Override
@@ -13,12 +15,14 @@ private int partition(int[] number, int left, int right) {
       while (left < right && number[right] >= pivot) {
         right--;
       }
-      number[left] = number[right];
-
       while (left < right && number[left] <= pivot) {
         left++;
       }
-      number[right] = number[left];
+      if (left < right) {
+        SortUtils.swap(number, left, right);
+        left++;
+        right--;
+      }
     }
     number[left] = pivot;
     return left;
@@ -54,12 +58,14 @@ private static <T extends Comparable<T>> int partition(T[] array, int left, int
       while (left < right && array[right].compareTo(pivot) >= 0) {
         right--;
       }
-      array[left] = array[right];
-
       while (left < right && array[left].compareTo(pivot) <= 0) {
         left++;
       }
-      array[right] = array[left];
+      if (left < right) {
+        SortUtils.swap(array, left, right);
+        left++;
+        right--;
+      }
     }
     array[left] = pivot;
     return left;
diff --git a/src/main/java/com/examplehub/sorts/SelectionSort.java b/src/main/java/com/examplehub/sorts/SelectionSort.java
@@ -1,5 +1,7 @@
 package com.examplehub.sorts;
 
+import com.examplehub.utils.SortUtils;
+
 public class SelectionSort implements Sort {
 
   @Override
@@ -12,9 +14,7 @@ public void sort(int[] numbers) {
         }
       }
       if (minIndex != i) {
-        int temp = numbers[i];
-        numbers[i] = numbers[minIndex];
-        numbers[minIndex] = temp;
+        SortUtils.swap(numbers, i, minIndex);
       }
     }
   }
diff --git a/src/main/java/com/examplehub/sorts/SelectionSortRecursion.java b/src/main/java/com/examplehub/sorts/SelectionSortRecursion.java
@@ -1,5 +1,7 @@
 package com.examplehub.sorts;
 
+import com.examplehub.utils.SortUtils;
+
 public class SelectionSortRecursion implements Sort {
 
   @Override
@@ -22,9 +24,7 @@ private void selectionSort(int[] numbers, int len) {
         }
       }
       if (maxIndex != len - 1) {
-        int temp = numbers[maxIndex];
-        numbers[maxIndex] = numbers[len - 1];
-        numbers[len - 1] = temp;
+        SortUtils.swap(numbers, len - 1, maxIndex);
       }
       selectionSort(numbers, len - 1);
     }
@@ -51,9 +51,7 @@ private <T extends Comparable<T>> void selectionSort(T[] numbers, int len) {
         }
       }
       if (maxIndex != len - 1) {
-        T temp = numbers[maxIndex];
-        numbers[maxIndex] = numbers[len - 1];
-        numbers[len - 1] = temp;
+        SortUtils.swap(numbers, len - 1, maxIndex);
       }
       selectionSort(numbers, len - 1);
     }
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;
   }
+
+  /**
+   * Swap two elements of array.
+   *
+   * @param array the array contains elements
+   * @param i the first index
+   * @param j the second index
+   */
+  public static void swap(int[] array, int i, int j) {
+    int temp = array[i];
+    array[i] = array[j];
+    array[j] = temp;
+  }
+
+  /**
+   * Swap two elements of array.
+   *
+   * @param array the array contains elements
+   * @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[] array, int i, int j) {
+    T temp = array[i];
+    array[i] = array[j];
+    array[j] = temp;
+  }
 }

Original file line number	Diff line number	Diff line change
`@@ -1,5 +1,7 @@`
`1`	`1`	`package com.examplehub.sorts;`
`2`	`2`
	`3`	`+import com.examplehub.utils.SortUtils;`
	`4`	`+`
`3`	`5`	`public class SelectionSort implements Sort {`
`4`	`6`
`5`	`7`	`@Override`
`@@ -12,9 +14,7 @@ public void sort(int[] numbers) {`
`12`	`14`	`}`
`13`	`15`	`}`
`14`	`16`	`if (minIndex != i) {`
`15`		`- int temp = numbers[i];`
`16`		`- numbers[i] = numbers[minIndex];`
`17`		`- numbers[minIndex] = temp;`
	`17`	`+ SortUtils.swap(numbers, i, minIndex);`
`18`	`18`	`}`
`19`	`19`	`}`
`20`	`20`	`}`