import java.io.*; import java.util.StringTokenizer; /** * Exercise assorted sorting algorithms * @author: Timothy Rolfe * Just exercising code, so everything is static or local. */ class CkSorts {//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 = 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() { String rtn = ""; try { rtn = console.readLine(); } catch (Exception e) { System.out.println(e); System.exit(-1); } return rtn; } 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; } /** * Driving main to exercise the sorting algorithms * * This throws IOException just to avoid the try/catch dance when * opening the output file. */ public static void main ( String [] args ) throws IOException { 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[5]; // five elapsed times File f = new File("Assorted.csv"); // Accumulate statistics PrintWriter fOut = new PrintWriter(new FileWriter(f)); 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]; fOut.println ("nPasses," + nPasses); fOut.println ("n,Arrays.sort,Heap,Merge,Quick,Opt.Quick"); 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; // Heap sort start = System.currentTimeMillis(); generator.setSeed(seed); for ( pass = 0; pass < nPasses; pass++ ) { shuffleArray ( test, size ); if (DISPLAY) showArray ( test, size ); HeapSort.heapSort ( 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; // Merge sort start = System.currentTimeMillis(); generator.setSeed(seed); for ( pass = 0; pass < nPasses; pass++ ) { shuffleArray ( test, size ); if (DISPLAY) showArray ( test, size ); MergeSort.mergeSort ( 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; // Straight quick sort start = System.currentTimeMillis(); generator.setSeed(seed); for ( pass = 0; pass < nPasses; pass++ ) { shuffleArray ( test, size ); if (DISPLAY) showArray ( test, size ); QuickSort.qSort ( test, size ); if ( CHECK && !sorted ( test, size ) ) { System.out.println("Sort failed. Abort in pass "+(pass+1)); break; } } // end for elapsed[3] = (System.currentTimeMillis() - start)/1000.0; // Optimized quick sort (inSort for small array segments) start = System.currentTimeMillis(); generator.setSeed(seed); for ( pass = 0; pass < nPasses; pass++ ) { shuffleArray ( test, size ); if (DISPLAY) showArray ( test, size ); QuickSort.qSortO ( test, size ); if ( CHECK && !sorted ( test, size ) ) { System.out.println("Sort failed. Abort in pass "+(pass+1)); break; } } // end for elapsed[4] = (System.currentTimeMillis() - start)/1000.0; if (DISPLAY) { System.out.println (""); showArray ( test, size ); } System.out.print (size); fOut.print (size); for ( int k = 0; k < elapsed.length; k++ ) { System.out.print ( "," + elapsed[k] ); fOut.print ( "," + elapsed[k] ); } System.out.println(); fOut.println(); fOut.flush(); size += sizeStep; // Next size } // end while ( size <= maxSize ) fOut.close(); } // 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 */ 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