/** * Exercise optimized sorting algorithms * @author: Timothy Rolfe * Just exercising code, so everything is static or local. */ import java.io.*; import java.util.StringTokenizer; class LongInsQ {//Random generator is seeded in main, but used in shuffle. static java.util.Random generator = new java.util.Random(); static boolean DISPLAY = false; // Display results static boolean CHECK = true ; // Check validity of sorting static final int CUTOFF = 20; // Length to shift to inSort 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; } /** * Optimized insertion sort * * insertion point is found by binary search * data movement in the array is done by System.arraycopy() */ public static void optInsSort ( Comparable[] x, int n ) { int lim, // start of unsorted region hole; // insertion point in sorted region for ( lim = 1 ; lim < n ; lim++ ) { Comparable save = x[lim]; hole = binSearch ( x, lim, save ); System.arraycopy(x, hole, x, hole+1, lim-hole); x[hole] = save; } // end for } // end optInsSort() /** * Binary search returns point where item IS or BELONGS. */ static int binSearch ( Comparable[] x, int n, Comparable val) { int lo = 0, hi = n-1; while (lo < hi) { int mid = (lo + hi) / 2; if (val.compareTo(x[mid]) > 0) lo = mid + 1; else hi = mid; } // end while if ( val.compareTo(x[hi]) > 0 ) // Belongs at the VERY end return n; else // Where val belongs (or is) return hi; } // end binSearch() /** * 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) { int mid; while (lo < hi) { 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 */ } } /** * 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." */ /* "Median of Three" --- middle element becomes the actual element. */ /* Insure that ends up in x[lo]. */ int mid; Comparable hold; if (lo >= hi) return 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 */ swap(lo, hi, x); else ; /* bac --- null statement */ else /* bca cab cba */ if (x[lo].compareTo(x[mid]) > 0) /* otherwise bca and no action */ if (x[mid].compareTo(x[hi]) > 0) /* cba */ swap(lo, mid, x); else /* cab */ swap(lo, hi, x); /* 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) {/*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; } /* 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 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 ); while ( size <= maxSize ) { long seed = generator.nextLong(); // Same sequence in all 3 // Array sort method from java.util.Arrays start = System.currentTimeMillis(); generator.setSeed(seed); for ( pass = 0; pass < nPasses; pass++ ) { shuffleArray ( test, size ); if (DISPLAY) showArray ( test, size ); // Note: from-index inclusive to to-index EXCLUSIVE java.util.Arrays.sort( test, 0, 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; // Optimized insertion sort start = System.currentTimeMillis(); generator.setSeed(seed); for ( pass = 0; pass < nPasses; pass++ ) { shuffleArray ( test, size ); if (DISPLAY) showArray ( test, size ); optInsSort ( 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; // Optimized quick sort start = System.currentTimeMillis(); generator.setSeed(seed); 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 ( Integer [] x, int lim ) { while ( lim > 1 ) { int item; Integer 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 LongInsQ class