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

1 /**
2 * Quicksort algorithm (driver)
3 */
4 public static <AnyType extends Comparable<? super AnyType>>
5 void quicksort( AnyType [ ] a )
6 {
7 quicksort( a, 0, a.length - 1 );
8 }
9
10 /**
11 * Internal quicksort method that makes recursive calls.
12 * Uses median-of-three partitioning and a cutoff.
13 */
14 private static <AnyType extends Comparable<? super AnyType>>
15 void quicksort( AnyType [ ] a, int low, int high )
16 {
17 if( low + CUTOFF > high )
18 insertionSort( a, low, high );
19 else
20 { // Sort low, middle, high
21 int middle = ( low + high ) / 2;
22 if( a[ middle ].compareTo( a[ low ] ) < 0 )
23 swapReferences( a, low, middle );
24 if( a[ high ].compareTo( a[ low ] ) < 0 )
25 swapReferences( a, low, high );
26 if( a[ high ].compareTo( a[ middle ] ) < 0 )
27 swapReferences( a, middle, high );
28
29 // Place pivot at position high - 1
30 swapReferences( a, middle, high - 1 );
31 AnyType pivot = a[ high - 1 ];
32
33 // Begin partitioning
34 int i, j;
35 for( i = low, j = high - 1; ; )
36 {
37 while( a[ ++i ].compareTo( pivot ) < 0 )
38 ;
39 while( pivot.compareTo( a[ --j ] ) < 0 )
40 ;
41 if( i >= j )
42 break;
43 swapReferences( a, i, j );
44 }
45 // Restore pivot
46 swapReferences( a, i, high - 1 );
47
48 quicksort( a, low, i - 1 ); // Sort small elements
49 quicksort( a, i + 1, high ); // Sort large elements
50 }
51 }

figure 8.22
Quicksort with
median-of-three
partitioning and cutoff
for small arrays