Sorting algorithms - Data Structures and Problem Solving Using Java - page 382

figure 8.23
Quickselect with
median-of-three
partitioning and cutoff
for small arrays

1 /**
2 * Internal selection method that makes recursive calls.
3 * Uses median-of-three partitioning and a cutoff.
4 * Places the kth smallest item in a[k-1].
5 * @param a an array of Comparable items.
6 * @param low the left-most index of the subarray.
7 * @param high the right-most index of the subarray.
8 * @param k the desired rank (1 is minimum) in the entire array.
9 */
10 private static <AnyType extends Comparable<? super AnyType>>
11 void quickSelect( AnyType [ ] a, int low, int high, int k )
12 {
13 if( low + CUTOFF > high )
14 insertionSort( a, low, high );
15 else
16 {
17 // Sort low, middle, high
18 int middle = ( low + high ) / 2;
19 if( a[ middle ].compareTo( a[ low ] ) < 0 )
20 swapReferences( a, low, middle );
21 if( a[ high ].compareTo( a[ low ] ) < 0 )
22 swapReferences( a, low, high );
23 if( a[ high ].compareTo( a[ middle ] ) < 0 )
24 swapReferences( a, middle, high );
25
26 // Place pivot at position high - 1
27 swapReferences( a, middle, high - 1 );
28 AnyType pivot = a[ high - 1 ];
29
30 // Begin partitioning
31 int i, j;
32 for( i = low, j = high - 1; ; )
33 {
34 while( a[ ++i ].compareTo( pivot ) < 0 )
35 ;
36 while( pivot.compareTo( a[ --j ] ) < 0 )
37 ;
38 if( i >= j )
39 break;
40 swapReferences( a, i, j );
41 }
42 // Restore pivot
43 swapReferences( a, i, high - 1 );
44
45 // Recurse; only this part changes
46 if( k <= i )
47 quickSelect( a, low, i - 1, k );
48 else if( k > i + 1 )
49 quickSelect( a, i + 1, high, k );
50 }
51 }