Quicksort help

so i was given a class, Quick, which is code for the quicksort algorithm. i am then given another class, QuickX, that shows quicksort with various modifications, including median of three, my task is to change the quick class to run with the median of three modification, the two classes are as follows:

package edu.princeton.cs.algs4;

/** * The {@code Quick} class provides static methods for sorting an * array and selecting the ith smallest element in an array using quicksort. *

* For additional documentation, see Section 2.1 of * Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. * * @author Robert Sedgewick * @author Kevin Wayne */ public class Quick {

// This class should not be instantiated. private Quick() { }

/** * Rearranges the array in ascending order, using the natural order. * @param a the array to be sorted */ public static void sort(Comparable[] a) { StdRandom.shuffle(a); sort(a, 0, a.length - 1); assert isSorted(a); }

// 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); assert isSorted(a, lo, 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; }

/** * Rearranges the array so that {@code a[k]} contains the kth smallest key; * {@code a[0]} through {@code a[k-1]} are less than (or equal to) {@code a[k]}; and * {@code a[k+1]} through {@code a[n-1]} are greater than (or equal to) {@code a[k]}. * * @param a the array * @param k the rank of the key * @return the key of rank {@code k} */ public static Comparable select(Comparable[] a, int k) { if (k < 0 || k >= a.length) { throw new IndexOutOfBoundsException("Selected element out of bounds"); } StdRandom.shuffle(a); int lo = 0, hi = a.length - 1; while (hi > lo) { int i = partition(a, lo, hi); if (i > k) hi = i - 1; else if (i < k) lo = i + 1; else return a[i]; } return a[lo]; }

/*************************************************************************** * Helper sorting functions. ***************************************************************************/ // is v < w ? private static boolean less(Comparable v, Comparable w) { 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. ***************************************************************************/ private static boolean isSorted(Comparable[] a) { return isSorted(a, 0, a.length - 1); }

private static boolean isSorted(Comparable[] a, int lo, int hi) { for (int i = lo + 1; i <= hi; i++) if (less(a[i], a[i-1])) return false; return true; }

// print array to standard output private static void show(Comparable[] a) { for (int i = 0; i < a.length; i++) { StdOut.println(a[i]); } }

/** * Reads in a sequence of strings from standard input; quicksorts them; * and prints them to standard output in ascending order. * Shuffles the array and then prints the strings again to * standard output, but this time, using the select method. * * @param args the command-line arguments */ public static void main(String[] args) { String[] a = StdIn.readAllStrings(); Quick.sort(a); show(a); assert isSorted(a);

// shuffle StdRandom.shuffle(a);

// display results again using select StdOut.println(); for (int i = 0; i < a.length; i++) { String ith = (String) Quick.select(a, i); StdOut.println(ith); } }

}

package edu.princeton.cs.algs4;

/** * The {@code QuickX} class provides static methods for sorting an * array using an optimized version of quicksort (using Bentley-McIlroy * 3-way partitioning, Tukey's ninther, and cutoff to insertion sort). *

* For additional documentation, see Section 2.1 of * Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. * * @author Robert Sedgewick * @author Kevin Wayne */ public class QuickX {

// cutoff to insertion sort, must be >= 1 private static final int INSERTION_SORT_CUTOFF = 8;

// cutoff to median-of-3 partitioning private static final int MEDIAN_OF_3_CUTOFF = 40;

// This class should not be instantiated. private QuickX() { }

/** * Rearranges the array in ascending order, using the natural order. * @param a the array to be sorted */ public static void sort(Comparable[] a) { sort(a, 0, a.length - 1); }

private static void sort(Comparable[] a, int lo, int hi) { int n = hi - lo + 1;

// cutoff to insertion sort if (n <= INSERTION_SORT_CUTOFF) { insertionSort(a, lo, hi); return; }

// use median-of-3 as partitioning element else if (n <= MEDIAN_OF_3_CUTOFF) { int m = median3(a, lo, lo + n/2, hi); exch(a, m, lo); }

// use Tukey ninther as partitioning element else { int eps = n/8; int mid = lo + n/2; int m1 = median3(a, lo, lo + eps, lo + eps + eps); int m2 = median3(a, mid - eps, mid, mid + eps); int m3 = median3(a, hi - eps - eps, hi - eps, hi); int ninther = median3(a, m1, m2, m3); exch(a, ninther, lo); }

// Bentley-McIlroy 3-way partitioning int i = lo, j = hi+1; int p = lo, q = hi+1; Comparable v = a[lo]; while (true) { while (less(a[++i], v)) if (i == hi) break; while (less(v, a[--j])) if (j == lo) break;

// pointers cross if (i == j && eq(a[i], v)) exch(a, ++p, i); if (i >= j) break;

exch(a, i, j); if (eq(a[i], v)) exch(a, ++p, i); if (eq(a[j], v)) exch(a, --q, j); }

i = j + 1; for (int k = lo; k <= p; k++) exch(a, k, j--); for (int k = hi; k >= q; k--) exch(a, k, i++);

sort(a, lo, j); sort(a, i, hi); }

// sort from a[lo] to a[hi] using insertion sort private static void insertionSort(Comparable[] a, int lo, int hi) { for (int i = lo; i <= hi; i++) for (int j = i; j > lo && less(a[j], a[j-1]); j--) exch(a, j, j-1); }

// return the index of the median element among a[i], a[j], and a[k] private static int median3(Comparable[] a, int i, int j, int k) { return (less(a[i], a[j]) ? (less(a[j], a[k]) ? j : less(a[i], a[k]) ? k : i) : (less(a[k], a[j]) ? j : less(a[k], a[i]) ? k : i)); }

/*************************************************************************** * Helper sorting functions. ***************************************************************************/ // is v < w ? private static boolean less(Comparable v, Comparable w) { return v.compareTo(w) < 0; }

// does v == w ? private static boolean eq(Comparable v, Comparable w) { 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. ***************************************************************************/ private static boolean isSorted(Comparable[] a) { for (int i = 1; i < a.length; i++) if (less(a[i], a[i-1])) return false; return true; }

// print array to standard output private static void show(Comparable[] a) { for (int i = 0; i < a.length; i++) { StdOut.println(a[i]); } }

/** * Reads in a sequence of strings from standard input; quicksorts them * (using an optimized version of quicksort); * and prints them to standard output in ascending order. * * @param args the command-line arguments */ public static void main(String[] args) { String[] a = StdIn.readAllStrings(); QuickX.sort(a); assert isSorted(a); show(a); }

}