Java Reference
In-Depth Information
Note:
Quick sort rearranges the entries in an array during the partitioning process. Each
partition places one entry—the pivot—in its correct sorted position. The entries in each of the
two subarrays that are before and after the pivot will remain in their respective subarrays.
Pivot selection.
Median-of-three pivot selection requires us to sort three entries. We do this with
simple comparisons and swaps, as follows:
/** Sorts the first, middle, and last entries of an array
into ascending order.
@param a an array of Comparable objects
@param first the integer index of the first array entry;
first >= 0 and < a.length
@param mid the integer index of the middle array entry
@param last the integer index of the last array entry;
last - first >= 2, last < a.length */
private static
<T
extends
Comparable<?
super
T>>
void
sortFirstMiddleLast(T[] a,
int
first,
int
mid,
int
last)
{
order(a, first, mid);
// make a[first] <= a[mid]
order(a, mid, last);
// make a[mid] <= a[last]
order(a, first, mid);
// make a[first] <= a[mid]
}
// end sortFirstMiddleLast
/** Orders two given array entries into ascending order
so that a[i] <= a[j].
@param a an array of Comparable objects
@param i an integer >= 0 and < array.length
@param j an integer >= 0 and < array.length */
private static
<T
extends
Comparable<?
super
T>>
void
order(T[] a,
int
i,
int
j)
{
if
(a[i].compareTo(a[j]) > 0)
swap(a, i, j);
}
// end order
/** Swaps the array entries array[i] and array[j]. */
private static void
swap(Object[] array,
int
i,
int
j)
{
Object temp = array[i];
array[i] = array[j];
array[j] = temp;
}
// end swap
After passing the indices of the first, middle, and last entries of the array to the method
sortFirstMiddleLast
, we will have the pivot at the middle index.
9.17
Partitioning.
Median-of-three pivot selection assumes that the array has at least three entries. If you have
only three entries, the pivot selection sorts them, so there is no need for the partition method or for quick
sort. Thus, the following partition method assumes that the array contains at least four entries:
/** Partitions an array as part of quick sort into two subarrays
called Smaller and Larger that are separated by a single
entry called the pivot.
Entries in Smaller are <= pivot and appear before the
pivot in the array.
Entries in Larger are >= pivot and appear after the
pivot in the array.
