asoftwareguy · July 5, 2011 12:49 · Jul 5, 2011
diff --git a/Quicksort.java b/Quicksort.java
@@ -0,0 +1,123 @@
+package example.sort;
+
+public final class Quicksort {
+
+  /**
+   * Sort the given array, calling the recursive sort method..
+   * 
+   * @param array
+   *          the array we are sorting
+   */
+  public static <T extends Comparable<T>> void sort(T[] array) {
+    recursiveSort(array, 0, array.length - 1);
+  }
+
+  /**
+   * Recursive sort function for quicksort.
+   * 
+   * @param array
+   *          the array we are sorting
+   * @param left
+   *          the left bound of the sublist of the array we are sorting
+   * @param right
+   *          the right bound of the sublist of the array we are sorting
+   */
+  private static <T extends Comparable<T>> void recursiveSort(T[] array, int left, int right) {
+    if (left == right) {
+      // already sorted
+      return;
+    }
+    // check that our left and right bounds haven't crossed over each other
+    if (left < right) {
+      // partition the array around the pivot
+      int pivotIdx = partition(array, left, right, selectInitialPivotIndex(array, left, right));
+      // recursively sort the left and right sublists
+      recursiveSort(array, left, pivotIdx - 1);
+      recursiveSort(array, pivotIdx + 1, right);
+    }
+  }
+
+  /**
+   * Select the initial pivot index. Uses median of 3 method.
+   * 
+   * @param array
+   *          the array from which to select a pivot index
+   * @param left
+   *          the left bound of the sublist of the array we are sorting
+   * @param right
+   *          the right bound of the sublist of the array we are sorting
+   * @return the initial pivot index
+   */
+  private static <T extends Comparable<T>> int selectInitialPivotIndex(T[] array, int left, int right) {
+    int center = (left + right) / 2;
+    // order left & center
+    if (array[left].compareTo(array[center]) > 0) {
+      swap(array, left, center);
+    }
+    // order left & right
+    if (array[left].compareTo(array[right]) > 0) {
+      swap(array, left, right);
+    }
+    // order center & right
+    if (array[center].compareTo(array[right]) > 0) {
+      swap(array, center, right);
+    }
+    // use the center (median)
+    return center;
+  }
+
+  /**
+   * Partition the array into L v R, where v is the pivot value, L is a sublist
+   * of values in the array that are less than or equal to v, and R is a sublist
+   * of values of the array that are greater than or equal to v.
+   * 
+   * @param array
+   *          the array to partition
+   * @param left
+   *          the left bound of the sublist of the array we are sorting
+   * @param right
+   *          the right bound of the sublist of the array we are sorting
+   * @param pivotIdx
+   *          the index of the pivot value, v
+   * @return
+   */
+  private static <T extends Comparable<T>> int partition(T[] array, int left, int right, int pivotIdx) {
+    // since we used the median of 3 method for finding the pivot, we already
+    // know that value at the far left is smaller than the pivot and the value
+    // at the far right is greater than the pivot. since we do not want to
+    // disturb these values while we traverse the list but we want to move the
+    // pivot out of the way , we move the pivot just to the left of the far
+    // right position
+    int index = left + 1;
+    int pivotSwap = right - 1;
+    swap(array, pivotIdx, pivotSwap);
+    // loop between the left+1 bound and the right-1 bound, comparing and
+    // swapping values less than the pivot value to the current index, and
+    // moving the index up one on each swap
+    for (int i = index; i < pivotSwap; i++) {
+      if ((array[i]).compareTo(array[pivotSwap]) <= 0) {
+        swap(array, i, index);
+        index++;
+      }
+    }
+    // restore the pivot to the newly found index
+    swap(array, pivotSwap, index);
+    return index;
+  }
+
+  /**
+   * Swap two values.
+   * 
+   * @param array
+   *          the array in which to swap two values
+   * @param i
+   *          the index of the first value to swap
+   * @param j
+   *          the index of the second value to swap
+   */
+  private static <T extends Comparable<T>> void swap(T[] array, int i, int j) {
+    T temp = array[i];
+    array[i] = array[j];
+    array[j] = temp;
+  }
+}