import java.util.Scanner; /** Testing routines for Quicksort */ class TestSort { private static Scanner in = new Scanner(System.in); // keyboard input with prompt private static String inputLine(String prompt) { System.out.print(prompt); return in.nextLine(); } // safe int input with prompt private static int inputInt(String prompt) { System.out.print(prompt); while (!in.hasNextInt()) { in.next(); in.nextLine(); System.out.print("Error, try again: "); } int val = in.nextInt(); in.nextLine(); return val; } /** interactive menu driven testing program for Baase's quicksort * and Knuth's, applied to integers. */ public static void main(String[] args) /// user chooses testing method in loop { System.out.println("User commands given by first letter:"); System.out.println(" Insertion sort parameter: check and adjust"); System.out.println(" Small test: test on a small fixed list"); System.out.println(" User test : test on a user-provided list"); System.out.println( " Many stats: many statistics on optimized quicksort"); System.out.println(" Quit : quit the program"); System.out.println(); String menu = "%nQ)uit; I)nsertion param: %d; S)mall test; U)ser test; M)any stats: "; char choice = Character.toUpperCase((inputLine(menu())+" ").charAt(0)); while ( choice != 'Q') { if (choice == 'I') setInsertionParam(); if (choice == 'S') smallTest(); else if (choice == 'U') userTest(); else if (choice == 'M') manyStats(); else System.out.println("Unknown choice " + choice); choice = Character.toUpperCase((inputLine(menu())+" ").charAt(0)); } } public static String menu() { String prompt = "%nQ)uit; I)nsertion param: %d; S)mall test; U)ser test; M)any stats: "; return String.format(prompt, Quicksort.MAX_INSERTION_SORT); } public static void printArray(int[] array) { // prints array, possibly on multiple lines String line = "{"; for (int i = 0; i < array.length; i++){ if (line.length() > 65) { System.out.println(line); line = " "; } line += array[i] + " "; } System.out.println(line + "}" ); } /** test quicksort on a fixed small array. */ public static void smallTest() { int[ ] data = { 1000, 80, 10, 50, 70, 60, 90, 20, 30, 40, 0, -1000 }; System.out.println("Here is the entire original array:"); printArray(data); Quicksort.quicksort(data, 1, data.length-2); System.out.println("I have sorted all but the first and last numbers."); System.out.println("The numbers are now:"); printArray(data); } /* test quicksort on data entered by user. */ public static void userTest() { int[] dataBig = new int[1000]; int size = 0; System.out.println("Enter numbers. Multiple lines are OK. End with q:"); while (in.hasNextInt()) { dataBig[size] = in.nextInt(); size++; } in.nextLine(); // clear illegal character and line int[] data = new int[size]; System.arraycopy(dataBig,0,data,0,size); System.out.println("Starting array:" ); printArray(data); // Sort the numbers, and print the result with blank after each number. int ver = inputInt( "Enter version: <3: current insert lim, >2: set insert lim: "); testSort(data, ver); System.out.println("The sorted numbers are:"); printArray(data); } /** fill an array with random numbers in range 0 .. nval-1. */ public static void randArray(int[] array, int nval) { // places random numbers in range 0 - nval-1 into array for (int i = 0; i < array.length; i++) array[i] = (int)(nval*Math.random()); } /** fill an array with numbers in order. * Direction -1, 0, 1 means decreasing, constant, increasing. */ public static void ordered(int[] array, int direction) { // fills array based on direction: // 0: 0,0,0, ... // 1: 0,1, 2, ... // -1: ... 2, 1, 0 int n = 0; if (direction < 0) n = array.length - 1; for (int i = 0; i < array.length; i++) { array[i] = n; n += direction; } } /** randomly redistribute fraction of an array. */ public static void garble(int[] array, double howMuch) { // swaps elements of array from random indices, // moving a proportion howMuch of the elements in array int nval = array.length; int nswap = (int)(nval*howMuch); int origIndex = (int)(nval*Math.random()); int thisVal = array[origIndex]; for (int i = 0; i < nswap; i++) { int lastVal = thisVal; int nextIndex = (int)(nval*Math.random()); thisVal = array[nextIndex]; array[nextIndex] = lastVal; } array[origIndex] = thisVal; } private static int MAX_TYPE = 6; private static String listgen(int[] array, int type) // different lists generated depending on parameter type, // returns description { switch(type) { case 0: { int nvals = (int)Math.sqrt(array.length); randArray(array, nvals); return String.format("random, %d values", nvals); } case 1: { randArray(array,10*array.length); return "random"; } case 2: { ordered(array, 1); return "in order"; } case 3: { ordered(array, 1); garble(array, .05); return "in order except for 5%"; } case 4: { ordered(array, -1); return "reversed order"; } case 5: { ordered(array, -1); garble(array, .05); return "reversed except for 5%"; } case 6: { ordered(array, 0); return "all same"; } } return "error"; } public static int checksum(int[] array) // sums numbers in list for a check: // not a complete test, but if the wrong numbers are in a "sorted" // list, their sum is likely to change from the original list { int sum = 0; for (int i = array.length - 1; i >= 0; i--) sum += array[i]; return sum; } /** Rreturns true if array in increasing order. */ public static boolean inorder(int[] array) { for (int i = 0; i < array.length - 1; i++) if( array[i] > array[i+1]) return false; return true; } /** adjust Insertion parameter: * <3: leave optimized version alone; * >=3: set Quicksort parameter to number given * return the resulting Quicksort Insertion parameter. */ public static int fixVersion(int ver) { if (ver < 3) ver = Quicksort.MAX_INSERTION_SORT; else Quicksort.MAX_INSERTION_SORT = ver; return ver; } /** Returns approximate time for quicksort version ver on array. */ public static long testSort(int[] array, int ver) { long time; int size; int sum; sum = checksum(array); time = System.currentTimeMillis(); ver = fixVersion(ver); Quicksort.quicksort(array, 0, array.length - 1); time = System.currentTimeMillis() - time; if (sum != checksum(array)) badExit("CHECKSUM ERROR!!! on version " + ver); if (!inorder(array)) { if (array.length < 100) printArray(array); badExit("NOT SORTED!!! on version " + ver); } return time; } private static final String STATFORMAT = "%7s"; private static void sortStatHeading() { for (String heading : new String[] {"Avg", "Low", "High"}) System.out.format(STATFORMAT, heading); System.out.println(" Version Description-----"); } private static void printSortStat(int[] array, int type, int ver) { Stats stat = sortStat(array, type, ver); for (long val : new long[] {stat.avg, stat.low, stat.high}) System.out.format(STATFORMAT, "" + val); System.out.println(stat.desc); } private static Stats sortStat(int[] array, int type, int ver) { // get statistics on times of 10 sorts of lists of given type // using sort version ver int nReps = 10; long tottime = 0; long lowtime = Long.MAX_VALUE; long hightime = Long.MIN_VALUE; long time; String desc = ""; ver = fixVersion(ver); String verString = " Insert < " + ver +"; "; for (int i = 0; i < nReps; i++) { desc = listgen(array, type); // printArray(array); time = testSort(array, ver); tottime += time; if (time < lowtime) lowtime = time; if (time > hightime) hightime = time; } return new Stats((tottime+5)/nReps, lowtime, hightime, verString + desc); } public static long timeForBigRandom(int ver, int size) { return sortStat(new int[2000000], 1, ver).avg; } /** set Quicksort insertion sort limit and test. */ public static void setInsertionParam() { int SIZE = 2000000; System.out.println("Enter an integer < 3 to stop."); int param = inputInt("Enter next quicksort insertion parameter > 2: "); while (param > 2) { param = fixVersion(param); System.out.println("Average ms to sort " + SIZE + ": " + timeForBigRandom(param, SIZE)); param = inputInt("Enter next quicksort insertion parameter: "); } } /** generates time statistics for many types of lists */ public static void manyStats() { int listSize = inputInt("Enter list size: "); int[] array = new int[listSize]; System.out.println("Sort times in millisecs, (10 times averaged), " + "list size " + listSize + ":"); sortStatHeading(); for (int type = 0; type <= MAX_TYPE; type++) { printSortStat(array, type, 0); } System.out.println(); } private static void badExit(String msg) { // called if program finds a bad sort when generating statistics System.out.println(msg); inputLine("Press return to abort! "); System.exit(1); } } class Stats { public long avg, low, high; public String desc; public Stats(long avg_, long low_, long high_, String desc_) { avg = avg_; low = low_; high = high_; desc = desc_; } }