Skip to content

Instantly share code, notes, and snippets.

@asoftwareguy
Created July 5, 2011 12:49
Show Gist options
  • Save asoftwareguy/1064785 to your computer and use it in GitHub Desktop.
Save asoftwareguy/1064785 to your computer and use it in GitHub Desktop.
Blog - QuickSort Example
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;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment