/** * 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 = 10; // Length to shift to inSort static int PIVOT; // front / random / median-of-three static final int OPTION = 0; // 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 methods. */ 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 ) { if ( OPTION == 0 ) { while ( lim > 1 ) { int item; Object save = x[lim-1]; item = generator.nextInt(lim); x[--lim] = x[item]; // Note predecrement on lim x[item] = save; } // end while } else if ( OPTION < 0 ) { int lo = 0, hi = lim-1; while ( lo < hi ) { Object temp = x[lo]; x[lo] = x[hi]; x[hi] = temp; hi--; lo++; } } // else leave sorted } // 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