Java Reference
In-Depth Information
@param a an array of Comparable objects
@param first the integer index of the first array entry;
first >= 0 and < a.length
@param last the integer index of the last array entry;
last - first >= 3; last < a.length
@return the index of the pivot */
private static
<T
extends
Comparable<?
super
T>>
int
partition(T[] a,
int
first,
int
last)
{
int
mid = (first + last) / 2;
sortFirstMiddleLast(a, first, mid, last);
// Assertion: The pivot is a[mid]; a[first] <= pivot and
// a[last] >= pivot, so do not compare these two array entries
// with pivot.
// move pivot to next-to-last position in array
swap(a, mid, last - 1);
int
pivotIndex = last - 1;
T pivot = a[pivotIndex];
// determine subarrays Smaller = a[first..endSmaller]
// and Larger = a[endSmaller+1..last-1]
// such that entries in Smaller are <= pivot and
// entries in Larger are >= pivot; initially, these subarrays are empty
int
indexFromLeft = first + 1;
int
indexFromRight = last - 2;
boolean
done =
false
;
while
(!done)
{
// starting at beginning of array, leave entries that are < pivot;
// locate first entry that is >= pivot; you will find one,
// since last entry is >= pivot
while
(a[indexFromLeft].compareTo(pivot) < 0)
indexFromLeft++;
// starting at end of array, leave entries that are > pivot;
// locate first entry that is <= pivot; you will find one,
// since first entry is <= pivot
while
(a[indexFromRight].compareTo(pivot) > 0)
indexFromRight--;
assert
a[indexFromLeft].compareTo(pivot) >= 0 &&
a[indexFromRight].compareTo(pivot) <= 0;
if
(indexFromLeft < indexFromRight)
{
swap(a, indexFromLeft, indexFromRight);
indexFromLeft++;
indexFromRight--;
}
else
done =
true
;
}
// end while
// place pivot between Smaller and Larger subarrays
swap(a, pivotIndex, indexFromLeft);
pivotIndex = indexFromLeft;
// Assertion:
//
Smaller = a[first..pivotIndex-1]
