Benchmarking of Pivot Selection Strategies
Timothy Rolfe
This is available as a Word document.
The detailed behavior of QuickSort depends on the strategy used for the selection of the pivot value within the Partition algorithm.
The fastest method is simply to accept the value at the beginning of the region being sorted. As Tony Hoare, the originator of QuickSort, noted in his original discussion of the algorithm[1], this is known to have disastrous results if the data being sorted are already ordered, either in a forward direction or reversed: QuickSort becomes an O(n2) algorithm rather than the average case as an O(n log n) algorithm.
One can avoid this worst-case behavior by choosing a random location within the region being sorted. This has the overhead of computing the random location — the method invocation of calling the random number generator, the integer arithmetic of computing the complete subscript, and the three assignment statements to swap the front element with that random element. This is actually in the original publication of the algorithm. [2]
Finally, Sedgewick [3] suggests a median-of-three algorithm. Assume that the region being sorted is defined by subscripts "lo" and "hi". Compute the midpoint subscript as "(lo+hi)/2". Perform the necessary comparisons and swaps to guarantee that the median of the three values is at x[lo]. Below is my implementation in Java, which sorts [lo], [mid], and [hi]:
mid = (lo + hi)
/ 2;
// We wish to move the median -- b in "abc" -- to position lo
if (x[lo].compareTo(x[hi]) < 0) // abc acb bac
if (x[lo].compareTo(x[mid]) < 0) // abc acb
if (x[mid].compareTo(x[hi]) < 0) // abc
swap(lo, mid, x);
else // acb --- place sentinels
{ swap(lo, hi, x); swap (mid, hi, x); }
else ; // bac --- null statement
else // bca cab cba
if (x[lo].compareTo(x[mid]) > 0) //
cab cba
if (x[mid].compareTo(x[hi]) > 0) // cba --- place sentinels
{ swap(lo, mid, x); swap (mid, hi, x); }
else // cab
swap(lo, hi, x);
else
swap(mid, hi, x); // bca: move c into place
On average, there are 8/3 invocations of compareTo: four permutations require three, while two require two. Seven swaps are performed across the six possible permutations. Thus we probably have a somewhat larger overhead than the random pivot. Given the complexity of the above, it might be preferable to use a pure three-comparison method with potentially three swaps, as given in Koffman's implementation.[4]
// "Three-sort" the entries in [lo], [mid], and [hi]
if ( x[mid].compareTo(x[lo]) < 0 )
swap ( lo, mid, x );
// assert: x[lo] <= x[mid]
if ( x[hi].compareTo(x[mid]) < 0 )
swap ( mid, hi, x );
// assert: x[hi] is the largest value of the three
if ( x[mid].compareTo(x[lo]) < 0 )
swap ( lo, mid, x );
// assert: x[lo] <= x[mid] <= x[hi]
// Begin partition logic: move partitioning element to [lo]
swap ( x, lo, mid );
The benchmark program uses a global variable "PIVOT" which contains 0, 1, or 2. Within the partition method, the pivot value is assumed to be in x[lo]. If PIVOT==1, a random location within the region [lo..hi] is swapped with x[lo]. If PIVOT==2, the above logic sets the median value into that location. The rest of the partition method uses an implementation I have taken from Thomas Naps [5] (and was included in Hoare's original discussion [1]).
The QuickSort implementation used includes two optimizations: (1) if the array segment to be sorted contains fewer than 10 entries, the insertion sort is used on it; (2) since the sorting of the right-hand segment is tail recursive, that recursive call is replaced by a loop depending on the update of parameters — the initial "if" becomes "while (hi > lo)", and the recursive call is replaced by the update "hi = mid + 1".
The main accepts from the user (or the command line) the initial array size, the final array size, the increment for the array size, and the number of random arrays to be averaged — given the current speed of computers, we cannot measure the time required to sort a single array except for sizes that would probably exceed physical memory available.
The data show that selection of a random pivot does indeed slow down the sorting, while the median-of-three speeds it up. The program was run on wyoming.ewu.edu, a computer with a single 2 GHz Intel® Pentium®–4 processor, within the Red Hat Linux and Java 1.4.2 environments.
Let "random" represent the time required for the random pivot; "front", the time required when the first element is accepted as the pivot; and "median", the time required for computing the median-of-three pivot. Then "random overhead" is given by "random/first – 1", and "median improvement" is given by "1 – median/front". The initial array size for this set was 100 — so that the three algorithms only took around half a second each. Small fluctuations here can have large effects because of the size of the numbers; hence the initial "median improvement" value.
Below is given the plot of the raw data that generated the above figure.
As usual, the best choice of an algorithm depends on the data that your program is likely to encounter. If there is a chance that the data will be sorted or nearly sorted, then the 8% overhead of the random pivot is a small price to pay for avoiding the O(n2) behavior. On the other hand, the expense of selecting the middle element rather than the first is minimal and provides quite effective protection against sorted data.
Then again, if you are assured that your data will not be sorted or nearly sorted, then you can achieve about a 5% speed-up by using the median-of-three partitioning strategy.
Charles Anthony Richard Hoare, Computer Journal, Vol 2 (1962), pp. 10-15.
Charles Anthony Richard Hoare, CACM, Vol 4, No. 7 (July 1961), pp. 321-22.
Robert Sedgewick, Algorithms in C; Parts 1-4 (3rd edition; Addison, Wesley, 1998), p. 319-24.
Elliot B. Koffman and Paul A. T. Wolfgang, Objects, Abstraction, Data Structures and Design using Java Version 5.0 (John Wiley & Sons, 2005), pp. 551-53.
Thomas L. Naps, Introduction to Data Structures and Algorithm Analysis (2nd edition; West Publishing Company, 1992), pp. 261-62.
Listing of Program Execution
— Click here to see as a csv fileInitial array length: 100 Maximum array length: 5000 Increment for length: 100 Number of passes: 10000 n,front,random,median of three 100,0.617,0.674,0.576 200,1.247,1.385,1.208 300,1.94,2.148,1.875 400,2.659,2.937,2.562 500,3.407,3.757,3.27 600,4.195,4.626,4.022 700,4.981,5.482,4.776 800,5.762,6.331,5.527 900,6.568,7.203,6.292 1000,7.375,8.088,7.068 1100,8.232,9.019,7.87 1200,9.063,9.93,8.67 1300,9.892,10.828,9.464 1400,10.729,11.745,10.269 1500,11.575,12.675,11.064 1600,12.451,13.623,11.902 1700,13.326,14.551,12.715 1800,14.182,15.487,13.536 1900,15.047,16.42,14.338 2000,15.912,17.393,15.184 2100,16.834,18.358,16.053 2200,17.713,19.306,16.863 2300,18.595,20.267,17.72 2400,19.494,21.237,18.553 2500,20.36,22.173,19.368 2600,21.273,23.159,20.221 2700,22.169,24.163,21.118 2800,23.075,25.096,21.969 2900,23.968,26.098,22.841 3000,24.928,27.077,23.664 3100,25.797,28.06,24.523 3200,26.738,29.083,25.396 3300,27.646,30.071,26.276 3400,28.568,31.07,27.149 3500,29.505,32.041,28.016 3600,30.41,33.042,28.888 3700,31.372,34.064,29.792 3800,32.275,35.117,30.685 3900,33.259,36.102,31.57 4000,34.16,37.138,32.41 4100,35.12,38.134,33.333 4200,36.14,39.233,34.302 4300,37.094,40.179,35.217 4400,38.019,41.266,36.095 4500,38.928,42.29,36.974 4600,39.906,43.275,37.829 4700,40.87,44.288,38.757 4800,41.84,45.355,39.668 4900,42.759,46.329,40.582 5000,43.735,47.397,41.452
CkPivot.java
— Click here for the file itself/**
* Exercise "choosePivot" options
*
* @author: Timothy Rolfe
*/
import java.io.*;
import java.util.StringTokenizer;
class CkPivot
{//Random generator is seeded in main, but used in shuffle.
static java.util.Random generator = new java.util.Random();
static final boolean DISPLAY = false; // Display results
static final boolean CHECK = true ; // Check validity of sorting
static final int CUTOFF = 20; // Length to shift to inSort
static int PIVOT; // front / random / median-of-three
static BufferedReader console = new BufferedReader
(new InputStreamReader(System.in));
static StringTokenizer tk = new StringTokenizer("");
/**
* Return one line from System.in
*/
static String readLine() throws Exception
{ return console.readLine(); }
static int readInt()
{
try
{
while (tk.countTokens() == 0 )
tk = new StringTokenizer(readLine());
return Integer.parseInt(tk.nextToken());
}
catch (Exception e)
{ System.out.println(e); System.exit(-1); }
return Integer.MIN_VALUE;
}
/**
* Public access to optimized quick sort
*/
public static void qSortO (Comparable [] x, int n)
{ qSortO(0, n-1, x); }
/**
* Optimized quick sort --- insertion sort for segments < CUTOFF
*/
static void qSortO(int lo, int hi, Comparable [] x)
{/* Basic QuickSort algorithm:
1) Check for exit condition: if hi does not come after lo,
there is nothing left to sort.
2) Let the "partition" function position one element to its
exact position: everything to its left belongs on the
left, everything to its right belongs on its right.
3) QuickSort can then call itself to sort everything to the
left as a sub-array.
4) Rather than recursively calling itself for the right
sub-array, QuickSort can just update lo and stay within
the current call, thus removing the tail recursion.
Note: Almost _all_ of the work for qSort is embedded in the
partition routine.
*/
int mid;
while (lo < hi) // while allows for removing tail recursion
{ if ( hi-lo < CUTOFF ) // Small case: Insert Sort
{ inSort(lo, hi, x); break; }
mid = partition(lo, hi, x);
qSortO(lo, mid - 1, x); // Recursive part for left
lo = mid + 1; // "Tail" recursion on right
} // end while
}
/**
* Swap two elements in an array --- used by partition
*/
static void swap (int lt, int rt, Object [] x)
{ Object tmp = x[lt]; x[lt] = x[rt]; x[rt] = tmp; }
/**
* Partition method used by quick sort.
*/
static int partition (int lo, int hi, Comparable [] x)
{/*Rearrange the x[] array so that a single element is properly
positioned: all elements to the left of the "partitioning
element" (or pivot) belong on the left; all to the right
belong on the right. The position of this partitioning
element is then the value of the partition function.
This version of partition based on Thomas Naps, "Introduction
to Data Structures and Algorithm Analysis"; the Median of Three
improvement is taken from Robert Sedgewick, "Algorithms."
*/
int mid;
Comparable hold;
if (lo >= hi) return hi;
if ( PIVOT == 1 ) // Random point chosen for pivot value
{
// Note: uses Math.random to avoid changing the sequence in generator
hold = x[lo];
mid = (int) (Math.random() * ((hi+1) - lo)) + lo;
x[lo] = x[mid];
x[mid] = hold;
}
else if ( PIVOT == 2 ) // Median-of-three value chosen for pivot value
{
// "Median of Three" --- middle element becomes the actual element.
// Insure that ends up in x[lo].
mid = (lo + hi) / 2;
// We wish to move the median -- b in "abc" -- to position lo
if (x[lo].compareTo(x[hi]) < 0) // abc acb bac
if (x[lo].compareTo(x[mid]) < 0) // abc acb
if (x[mid].compareTo(x[hi]) < 0) // abc
swap(lo, mid, x);
else // acb --- place sentinels
{ swap(lo, hi, x); swap (mid, hi, x); }
else ; // bac --- null statement
else // bca cab cba
if (x[lo].compareTo(x[mid]) > 0) // cab cba
if (x[mid].compareTo(x[hi]) > 0) // cba --- place sentinels
{ swap(lo, mid, x); swap (mid, hi, x); }
else // cab
swap(lo, hi, x);
else
swap(mid, hi, x); // bca: move c into place
}
// Open up a "hole" at x[lo], with median as pivot value
hold = x[lo];
// The loop has two exits: the two places where the lo and the hi
// indexes have come together. In lieu of extra flags or logical
// comparisons, this code uses an explicit "break" at those two places.
while (true) // Note: "break" out when (lo == hi)
{//Search for the value from hi downward to plug the hole at x[lo]
while (hold.compareTo(x[hi]) < 0 && lo < hi)
hi = hi - 1;
// If we've come together, we're done
if (lo == hi) break;
// Otherwise plug the hole at lo with the value at hi
x[lo] = x[hi];
// The hole is now at hi and lo is guaranteed good w.r.t. Pivot
lo = lo + 1;
// Search for the value from lo upward to plug the hole at x[hi]
while (x[lo].compareTo(hold) < 0 && lo < hi)
lo = lo + 1;
// If we've come together, we're done
if (lo == hi) break;
// Otherwise plug the hole at hi with the value at lo
x[hi] = x[lo];
// The hole is now at lo and hi is guaranteed good w.r.t. Pivot
hi = hi - 1;
} // end "infinite" while loop --- (lo == hi) became true
// Plug the remaining hole (which is guaranteed to be in hi = lo)
// with the pivot value, making this the partitioning element.
x[hi] = hold;
return hi;
}
/**
* Insertion sort method, used by qSortO
*/
public static void inSort ( int lo, int hi, Comparable[] x )
{ int lim, // start of unsorted region
hole; // insertion point in sorted region
for ( lim = lo+1 ; lim <= hi ; lim++ )
{ Comparable save = x[lim];
for ( hole = lim ;
hole > lo && save.compareTo(x[hole-1]) < 0 ;
hole-- )
{ x[hole] = x[hole-1]; }
x[hole] = save;
} // end for (lim...
} // end inSort()
/**
* Driving main to exercise the quick sort algorithms
*/
public static void main ( String [] args )
{ Integer [] test; // Array of int objects
int size, maxSize, sizeStep; // control outer loop
int nPasses, pass; // inner loop
double start, // initial times in msec.
elapsed[] = new double[3]; // three elapsed times
System.out.print ("Initial array length: ");
if ( args.length < 1 )
size = readInt();
else
{ size = Integer.parseInt(args[0]);
System.out.println ("" + size);
} // end if/else regarding args[0]
System.out.print ("Maximum array length: ");
if ( args.length < 2 )
maxSize = readInt();
else
{ maxSize = Integer.parseInt(args[1]);
System.out.println ("" + maxSize);
} // end if/else regarding args[1]
System.out.print ("Increment for length: ");
if ( args.length < 3 )
sizeStep = readInt();
else
{ sizeStep = Integer.parseInt(args[2]);
System.out.println ("" + sizeStep);
} // end if/else regarding args[2]
if ( DISPLAY )
nPasses = 1;
else
{ System.out.print ("Number of passes: ");
if ( args.length < 4 )
nPasses = readInt();
else
{ nPasses = Integer.parseInt(args[3]);
System.out.println ("" + nPasses);
} // end if/else regarding args[3]
} // end if/else
test = new Integer [maxSize];
fillArray ( test );
System.out.println ("n,front,random,median-of-three");
while ( size <= maxSize )
{ long seed = generator.nextLong(); // Same sequence in all 3
// Partition uses first item as pivot
start = System.currentTimeMillis();
generator.setSeed(seed);
PIVOT = 0;
for ( pass = 0; pass < nPasses; pass++ )
{ shuffleArray ( test, size );
if (DISPLAY)
showArray ( test, size );
qSortO ( test, size );
if ( CHECK && !sorted ( test, size ) )
{ System.out.println("Sort failed. Abort in pass "+(pass+1));
break;
}
} // end for
elapsed[0] = (System.currentTimeMillis() - start)/1000.0;
// Partition uses a random pivot
start = System.currentTimeMillis();
generator.setSeed(seed);
PIVOT = 1;
for ( pass = 0; pass < nPasses; pass++ )
{ shuffleArray ( test, size );
if (DISPLAY)
showArray ( test, size );
qSortO ( test, size );
if ( CHECK && !sorted ( test, size ) )
{ System.out.println("Sort failed. Abort in pass "+(pass+1));
break;
}
} // end for
elapsed[1] = (System.currentTimeMillis() - start)/1000.0;
// Partition uses median-of-three for pivot
start = System.currentTimeMillis();
generator.setSeed(seed);
PIVOT = 2;
for ( pass = 0; pass < nPasses; pass++ )
{ shuffleArray ( test, size );
if (DISPLAY)
showArray ( test, size );
qSortO ( test, size );
if ( CHECK && !sorted ( test, size ) )
{ System.out.println("Sort failed. Abort in pass "+(pass+1));
break;
}
} // end for
elapsed[2] = (System.currentTimeMillis() - start)/1000.0;
if (DISPLAY)
{ System.out.println ("");
showArray ( test, size );
}
System.out.print (size+"");
for ( int k = 0; k < elapsed.length; k++ )
System.out.print ( "," + elapsed[k] );
System.out.println("");
size += sizeStep; // Next size
} // end while ( size <= maxSize )
} // end main()
/**
* Fill the array with increasing sequence starting at 1
*/
static void fillArray ( Integer [] x )
{ for ( int k = 0; k < x.length; k++ )
x[k] = new Integer(k+1);
} // end fillArray()
/**
* Shuffle the entire array, using the class scope generator
*
* See Rolfe, Timothy. "Algorithm Alley: Randomized Shuffling",
* Dr. Dobb’s Journal, Vol. 25, No. 1 (January 2000), pp. 113-14.
*/
static void shuffleArray ( Object [] x, int lim )
{ while ( lim > 1 )
{ int item;
Object save = x[lim-1];
// For Java prior to version 1.1
// item = (int) ( generator.nextDouble() * lim );
// For Java from version 1.2 on
item = generator.nextInt(lim);
x[--lim] = x[item]; // Note predecrement on lim
x[item] = save;
} // end while
} // end shuffleArray()
/**
* Display in lines of 10 values --- if DISPLAY is true
*/
static void showArray ( Integer [] x, int lim )
{ int k;
for ( k = 0; k < lim; k++ )
{ StringBuffer front = new StringBuffer(" ");
String back = "" + x[k].intValue();
front.setLength(front.length()-back.length());
System.out.print (front+back);
if ( (k+1) % 10 == 0 )
System.out.println("");
} // end for
if ( k % 10 != 0 )
System.out.println("");
} // end showArray()
/**
* Verify that the array is correctly sorted --- if CHECK is true
*/
static boolean sorted ( Comparable[] x, int n )
{ for ( int k = 1; k < n; k++ )
if ( x[k-1].compareTo(x[k]) > 0 )
return false;
return true;
} // end sorted()
} // end QsortArray