Original Quick.java:

/****************************************************************************** * Compilation: javac Quick.java * Execution: java Quick < input.txt * Dependencies: StdOut.java StdIn.java * * % more tiny.txt * S O R T E X A M P L E * * % java Quick < tiny.txt * A E E L M O P R S T X [ one string per line ] ******************************************************************************/

public class Quick {

public static void sort(Comparable[] a) { sort(a, 0, a.length - 1); }

// quicksort the subarray from a[lo] to a[hi] private static void sort(Comparable[] a, int lo, int hi) { if (hi <= lo) return; int j = partition(a, lo, hi); sort(a, lo, j-1); sort(a, j+1, hi); }

// partition the subarray a[lo..hi] so that a[lo..j-1] <= a[j] <= a[j+1..hi] // and return the index j. private static int partition(Comparable[] a, int lo, int hi) { int i = lo; int j = hi + 1; Comparable v = a[lo]; while (true) {

// find item on lo to swap while (less(a[++i], v)) { if (i == hi) break; }

// find item on hi to swap while (less(v, a[--j])) { if (j == lo) break; // redundant since a[lo] acts as sentinel }

// check if pointers cross if (i >= j) break;

exch(a, i, j); }

// put partitioning item v at a[j] exch(a, lo, j);

// now, a[lo .. j-1] <= a[j] <= a[j+1 .. hi] return j; }

/*************************************************************************** * Helper sorting functions. ***************************************************************************/ // is v < w ? private static boolean less(Comparable v, Comparable w) { if (v == w) return false; // optimization when reference equals return v.compareTo(w) < 0; } // exchange a[i] and a[j] private static void exch(Object[] a, int i, int j) { Object swap = a[i]; a[i] = a[j]; a[j] = swap; }

/*************************************************************************** * Check if array is sorted - useful for debugging. ***************************************************************************/ // print array to standard output private static void show(Comparable[] a) { for (int i = 0; i < a.length; i++) { StdOut.println(a[i]); } }

public static void main(String[] args) { String[] a = StdIn.readAllStrings(); Quick.sort(a); show(a); }

}

Could you please revise or add to the original Quick.java program above to count precise number of compares and output results such as the ones below.

Before QuickSort: T L E X E A P R S M O

After QuickSort: A E E L M O P R S T X

There are 41 compares. NlgN = 38.05374780501027

Before QuickSort: Q U I C K S O R T E X A M P L E

After QuickSort: A C E E I K L M O P Q R S T U X

There are 71 compares. NlgN = 64