/* Purpose: This program illustrates sorting using the recursive quicksort algorithm. It attempts to display a trace of the recursive calls to the quickSort method by adding a parameter for the current level of recursive invocation, and using that to print the level in output and to tab over to the right to visually display the level of recursive invocation. There are helper methods for intializing an array to contain random integers in a specified range, to print an array, to print the indices of an array, and to insert space at the beginning of a new line. These methods are invoked from within the enhanced quickSort method, making it rather awkward to trace the code (as opposed to its execution). The goal was to show the structure both of recursive calls in the output, and illustrate the action of the quickSort algorithm. In order to make it easier to read the quickSort code, a version of the method without extra output statements is included, called pureQuickSort. Record of revisions: Date Programmer Description of change ==== ========== ===================== 18 March 2002 J. Rodger Original coding 20 March 2002 J. Rodger Add Quick Sort trace printing 25 March 2002 J. Rodger Additional recursive tracing 31 May 2002 J. Rodger adapt for hsa package 27 February 2003 J. Rodger minor parameter name changes add pureQuickSort method 03 March 2003 J. Rodger additional cleanup 06 March 2003 J. Rodger add sort of array shown in ppt slides 23 May 2003 J. Rodger eliminate non-hsa I/O */ import hsa.*; public class QuickSortIllustration { // exchanges elements i and j of the array, no error testing public static void swap (int i, int j, int [] sortArray) { int temp; temp = sortArray [i]; sortArray [i] = sortArray [j]; sortArray [j] = temp; } // end method swap // insert specified number of tabs at beginning of a new line public static void tabOver (int num) { Stdout.println (); for (int i = 0 ; i < num ; i++) Stdout.print (" "); } // end tabOver // uses the Math.random method & maps the value it returns // into a pseudorandom int in the range lo <= value returned <= hi public static int randInt (int lo, int hi) { return (int) Math.rint (Math.random () * (hi - lo)) + lo; } // prints the specified range of values in an array of integers public static void printArray2 (int [] sortArray, int first, int last) { int i = 0; for (i = first ; i <= last ; i++) { Stdout.print (sortArray [i], 3); } // end for } // end method printArray2 // print index values for sort array public static void printIndices (int level, String msg, int [] arr, int lo, int hi) { tabOver (level); for (int s = 0 ; s < msg.length () ; s++) Stdout.print (" "); for (int i = lo ; i <= hi ; i++) { Stdout.print (i, 3); } } // end printIndices // a simple recursive method implementing quicksort // no output display of recursive trace public static void pureQuickSort (int left, int right, int [] x) { int i = left, j = right, pVal; // use middle value of current partition to split it pVal = x [(left + right) / 2]; do { // move index markers towards middle // so long as values conform to partition while (x [i] < pVal) i++; while (x [j] > pVal) j--; // swap "out of partition" elements if (i <= j) { // this just avoids "empty" swap if i == j if (i < j) { swap (i, j, x); } // move index markers i++; j--; } // end if } while (i <= j); // invoke quicksort with resulting partitions if (left < j) { pureQuickSort (left, j, x); } if (i < right) { pureQuickSort (i, right, x); } } // end pureQuickSort method // a recursive method implementing quicksort, with enhanced output // parameters are the left (lower) and right (upper) // bounds of the part of the array to sort & the array itself // this version adds a counter to indicate the level of recursive nesting public static void quickSort (int l, int r, int [] sortArray, int level) { int i = l, j = r, pVal; // use middle value of current partition to split it pVal = sortArray [(l + r) / 2]; tabOver (level); Stdout.print ("Recursive depth:" + level); tabOver (level); Stdout.print ("Before partitioning:"); printArray2 (sortArray, l, r); printIndices (level, "Before partitioning:", sortArray, l, r); tabOver (level); Stdout.print ("i:" + l + ", j:" + j + ", Pval: " + pVal); do { // move index markers towards middle // so long as values conform to partition while (sortArray [i] < pVal) i++; while (sortArray [j] > pVal) j--; // swap "out of partition" elements if (i <= j) { // this just avoids "empty" swap if i == j if (i < j) { tabOver (level); Stdout.print ("Swap: " + sortArray [i] + " & " + sortArray [j]); Stdout.print (", (i=" + i + " j=" + j + ")"); swap (i, j, sortArray); } // move index markers i++; j--; } // end if } while (i <= j); tabOver (level); Stdout.print ("After partitioning:"); printArray2 (sortArray, l, r); printIndices (level, "After partitioning:", sortArray, l, r); // invoke quicksort with resulting partitions if (l < j) { tabOver (level); Stdout.print ("Recurse on left partition: l=" + l + " j=" + j); quickSort (l, j, sortArray, level + 1); } else { tabOver (level); Stdout.print ("No left (l=" + l + " j=" + j + ")"); } if (i < r) { tabOver (level); Stdout.print ("Recurse on right partition: i=" + i + " r=" + r); quickSort (i, r, sortArray, level + 1); } else { tabOver (level); Stdout.print ("No right (i=" + i + " r=" + r + ")"); } tabOver (level); Stdout.print ("Exit level:" + level); } // end quickSort method public static void main (String [] args) { // declare & initialize array to sort int [] x = new int [16]; for (int i = 0 ; i < x.length ; i++) x [i] = randInt (10, 99); Stdout.println ("\nBegin Quicksort"); quickSort (0, x.length - 1, x, 0); Stdout.println ("\nEnd Quicksort"); Stdout.print ("Array contents:"); printArray2 (x, 0, x.length - 1); printIndices (0, "Array contents:", x, 0, x.length - 1); Stdout.print ("\n\nShow Quick Sort operation on same array "); Stdout.println ("as in QuickSortIllustration.ppt"); Stdout.print ("Press \"Enter\" to continue:"); String junk = Stdin.readLine (); Stdout.println ("\n\n"); int [] y = {24, 17, 2, 66, 43, 21, 5, 91, 9, 14, 18}; quickSort (0, y.length - 1, y, 0); } // end method main } // end Class QuickSortIllustration