/** * Exercise insertion sorting algorithms * @author: Timothy Rolfe * Just exercising code, so everything is static or local. */ import java.io.*; import java.util.StringTokenizer; class InsArray {//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 = false; // Check validity of sorting 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; } /** * Straight insertion sort method */ public static void insSort ( 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]; for ( hole = lim ; hole > 0 && save.compareTo(x[hole-1]) < 0 ; hole-- ) { x[hole] = x[hole-1]; } x[hole] = save; } // end for (lim... } // end insSort() /** * 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 is (or belongs) return hi; } // end binSearch() // 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 (timing) 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; // Straight insertion sort start = System.currentTimeMillis(); generator.setSeed(seed); for ( pass = 0; pass < nPasses; pass++ ) { shuffleArray ( test, size ); if (DISPLAY) showArray ( test, size ); insSort ( 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; // Insertion sort optimed by binSearch and arraycopy 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[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 InsArray class