EXPERIMENTS 2.2.28 Top-down vs. bottom-up. Use SortCompare.java to compare top-down mergesort and bottom-up mergesort for N = 10 ^ 3

N = 10 ^ 4

N = 10 ^ 5

N = 10 ^ 6 /****************************************************************************** * Compilation: javac SortCompare.java * Execution: java SortCompare alg1 alg2 n trials * Dependencies: StdOut.java Stopwatch.java * * Sort n random real numbers, trials times using the two * algorithms specified on the command line. * * % java SortCompare Insertion Selection 1000 100 * For 1000 random Doubles * Insertion is 1.7 times faster than Selection * * Note: this program is designed to compare two sorting algorithms with * roughly the same order of growth, e,g., insertion sort vs. selection * sort or mergesort vs. quicksort. Otherwise, various system effects * (such as just-in-time compiliation) may have a significant effect. * One alternative is to execute with "java -Xint", which forces the JVM * to use interpreted execution mode only. * ******************************************************************************/ import java.util.Arrays; public class SortCompare { public static double time(String alg, Double[] a) { Stopwatch sw = new Stopwatch(); if (alg.equals("Insertion")) Insertion.sort(a); else if (alg.equals("InsertionX")) InsertionX.sort(a); else if (alg.equals("BinaryInsertion")) BinaryInsertion.sort(a); else if (alg.equals("Selection")) Selection.sort(a); else if (alg.equals("Bubble")) Bubble.sort(a); else if (alg.equals("Shell")) Shell.sort(a); else if (alg.equals("Merge")) Merge.sort(a); else if (alg.equals("MergeX")) MergeX.sort(a); else if (alg.equals("MergeBU")) MergeBU.sort(a); else if (alg.equals("Quick")) Quick.sort(a); else if (alg.equals("Quick3way")) Quick3way.sort(a); else if (alg.equals("QuickX")) QuickX.sort(a); else if (alg.equals("Heap")) Heap.sort(a); else if (alg.equals("System")) Arrays.sort(a); else throw new IllegalArgumentException("Invalid algorithm: " + alg); return sw.elapsedTime(); } // Use alg to sort trials random arrays of length n. public static double timeRandomInput(String alg, int n, int trials) { double total = 0.0; Double[] a = new Double[n]; // Perform one experiment (generate and sort an array). for (int t = 0; t < trials; t++) { for (int i = 0; i < n; i++) a[i] = StdRandom.uniform(0.0, 1.0); total += time(alg, a); } return total; } // Use alg to sort trials random arrays of length n. public static double timeSortedInput(String alg, int n, int trials) { double total = 0.0; Double[] a = new Double[n]; // Perform one experiment (generate and sort an array). for (int t = 0; t < trials; t++) { for (int i = 0; i < n; i++) a[i] = 1.0 * i; total += time(alg, a); } return total; } public static void main(String[] args) { String alg1 = args[0]; String alg2 = args[1]; int n = Integer.parseInt(args[2]); int trials = Integer.parseInt(args[3]); double time1, time2; if (args.length == 5 && args[4].equals("sorted")) { time1 = timeSortedInput(alg1, n, trials); // Total for alg1. time2 = timeSortedInput(alg2, n, trials); // Total for alg2. } else { time1 = timeRandomInput(alg1, n, trials); // Total for alg1. time2 = timeRandomInput(alg2, n, trials); // Total for alg2. } StdOut.printf("For %d random Doubles %s is", n, alg1); StdOut.printf(" %.1f times faster than %s ", time2/time1, alg2); } } /****************************************************************************** * Compilation: javac Merge.java * Execution: java Merge < input.txt * Dependencies: StdOut.java StdIn.java * Data files: https://algs4.cs.princeton.edu/22mergesort/tiny.txt * https://algs4.cs.princeton.edu/22mergesort/words3.txt * * Sorts a sequence of strings from standard input using mergesort. * * % more tiny.txt * S O R T E X A M P L E * * % java Merge < tiny.txt * A E E L M O P R S T X [ one string per line ] * * % more words3.txt * bed bug dad yes zoo ... all bad yet * * % java Merge < words3.txt * all bad bed bug dad ... yes yet zoo [ one string per line ] * ******************************************************************************/ /** * The {@code Merge} class provides static methods for sorting an * array using mergesort. * 
 * For additional documentation, see Section 2.2 of * Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. * For an optimized version, see {@link MergeX}. * * @author Robert Sedgewick * @author Kevin Wayne */ public class Merge { // This class should not be instantiated. private Merge() { } // stably merge a[lo .. mid] with a[mid+1 ..hi] using aux[lo .. hi] private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) { // precondition: a[lo .. mid] and a[mid+1 .. hi] are sorted subarrays assert isSorted(a, lo, mid); assert isSorted(a, mid+1, hi); // copy to aux[] for (int k = lo; k <= hi; k++) { aux[k] = a[k]; } // merge back to a[] int i = lo, j = mid+1; for (int k = lo; k <= hi; k++) { if (i > mid) a[k] = aux[j++]; else if (j > hi) a[k] = aux[i++]; else if (less(aux[j], aux[i])) a[k] = aux[j++]; else a[k] = aux[i++]; } // postcondition: a[lo .. hi] is sorted assert isSorted(a, lo, hi); } // mergesort a[lo..hi] using auxiliary array aux[lo..hi] private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) { if (hi <= lo) return; int mid = lo + (hi - lo) / 2; sort(a, aux, lo, mid); sort(a, aux, mid + 1, hi); merge(a, aux, lo, mid, hi); } /** * Rearranges the array in ascending order, using the natural order. * @param a the array to be sorted */ public static void sort(Comparable[] a) { Comparable[] aux = new Comparable[a.length]; sort(a, aux, 0, a.length-1); assert isSorted(a); } /*************************************************************************** * Helper sorting function. ***************************************************************************/ // is v < w ? private static boolean less(Comparable v, Comparable w) { return v.compareTo(w) < 0; } /*************************************************************************** * 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; } /*************************************************************************** * Index mergesort. ***************************************************************************/ // stably merge a[lo .. mid] with a[mid+1 .. hi] using aux[lo .. hi] private static void merge(Comparable[] a, int[] index, int[] aux, int lo, int mid, int hi) { // copy to aux[] for (int k = lo; k <= hi; k++) { aux[k] = index[k]; } // merge back to a[] int i = lo, j = mid+1; for (int k = lo; k <= hi; k++) { if (i > mid) index[k] = aux[j++]; else if (j > hi) index[k] = aux[i++]; else if (less(a[aux[j]], a[aux[i]])) index[k] = aux[j++]; else index[k] = aux[i++]; } } /** * Returns a permutation that gives the elements in the array in ascending order. * @param a the array * @return a permutation {@code p[]} such that {@code a[p[0]]}, {@code a[p[1]]}, * ..., {@code a[p[N-1]]} are in ascending order */ public static int[] indexSort(Comparable[] a) { int n = a.length; int[] index = new int[n]; for (int i = 0; i < n; i++) index[i] = i; int[] aux = new int[n]; sort(a, index, aux, 0, n-1); return index; } // mergesort a[lo..hi] using auxiliary array aux[lo..hi] private static void sort(Comparable[] a, int[] index, int[] aux, int lo, int hi) { if (hi <= lo) return; int mid = lo + (hi - lo) / 2; sort(a, index, aux, lo, mid); sort(a, index, aux, mid + 1, hi); merge(a, index, aux, lo, mid, hi); } // 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; mergesorts them; * 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(); Merge.sort(a); show(a); } } /****************************************************************************** * Compilation: javac MergeBU.java * Execution: java MergeBU < input.txt * Dependencies: StdOut.java StdIn.java * Data files: https://algs4.cs.princeton.edu/22mergesort/tiny.txt * https://algs4.cs.princeton.edu/22mergesort/words3.txt * * Sorts a sequence of strings from standard input using * bottom-up mergesort. * * % more tiny.txt * S O R T E X A M P L E * * % java MergeBU < tiny.txt * A E E L M O P R S T X [ one string per line ] * * % more words3.txt * bed bug dad yes zoo ... all bad yet * * % java MergeBU < words3.txt * all bad bed bug dad ... yes yet zoo [ one string per line ] * ******************************************************************************/ /** * The {@code MergeBU} class provides static methods for sorting an * array using bottom-up mergesort. * 
 * 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 MergeBU { // This class should not be instantiated. private MergeBU() { } // stably merge a[lo..mid] with a[mid+1..hi] using aux[lo..hi] private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) { // copy to aux[] for (int k = lo; k <= hi; k++) { aux[k] = a[k]; } // merge back to a[] int i = lo, j = mid+1; for (int k = lo; k <= hi; k++) { if (i > mid) a[k] = aux[j++]; // this copying is unneccessary else if (j > hi) a[k] = aux[i++]; else if (less(aux[j], aux[i])) a[k] = aux[j++]; else a[k] = aux[i++]; } } /** * Rearranges the array in ascending order, using the natural order. * @param a the array to be sorted */ public static void sort(Comparable[] a) { int n = a.length; Comparable[] aux = new Comparable[n]; for (int len = 1; len < n; len *= 2) { for (int lo = 0; lo < n-len; lo += len+len) { int mid = lo+len-1; int hi = Math.min(lo+len+len-1, n-1); merge(a, aux, lo, mid, hi); } } assert isSorted(a); } /*********************************************************************** * Helper sorting functions. ***************************************************************************/ // is v < w ? private static boolean less(Comparable v, Comparable w) { return v.compareTo(w) < 0; } /*************************************************************************** * 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; bottom-up * mergesorts them; 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(); MergeBU.sort(a); show(a); } }