<![CDATA[
CSE143 Quicksort Code handout #29
// pre : 0 <= index1, index2 < list.length
// post: Values of list[x] and list[y] are exchanged.
private static void swap(int[] list, int index1, int index2) {
int temp = list[index1];
list[index1] = list[index2];
list[index2] = temp;
}
// post: uses the middle value of the list as a "pivot" to
// partition the list into two sublists: all those values less
// than or equal to the pivot appearing first followed by the
// pivot followed by all those values greater than the pivot;
// places the pivot value between the two sublists and returns
// the index of the pivot value
private static int partition(int[] list, int low, int high) {
// swap middle value into first position
swap(list, low, (low + high) / 2);
// remember pivot
int pivot = list[low];
// loop invariant: list divided into 3 parts: values <= pivot followed
// by unknown values followed by values > pivot
int index1 = low + 1; // index of first unknown value
int index2 = high; // index of last unknown value
while (index1 <= index2) // while some values still unknown
if (list[index1] <= pivot)
index1++;
else if (list[index2] > pivot)
index2--;
else {
swap(list, index1, index2);
index1++;
index2--;
}
// put the pivot value between the two sublists and return its index
swap(list, low, index2);
return index2;
}
// post: elements low through high of given list are in sorted
// (nondecreasing) order
public static void sort(int[] list, int low, int high) {
// uses recursive quicksort to sort elements low through high; base
// case is a list of 0 or 1 elements, which requires no sorting; in
// recursive case, the list is partitioned using a pivot value and the
// two resulting lists are recursively sorted
if (low < high) {
int pivotIndex = partition(list, low, high);
sort(list, low, pivotIndex - 1);
sort(list, pivotIndex + 1, high);
}
}
// post: given list is in sorted (nondecreasing) order
public static void sort(int[] list) {
sort(list, 0, list.length - 1);
}
]]>