001package algs21; 002import stdlib.*; 003import algs22.*; 004import algs23.*; 005import algs24.*; 006/* *********************************************************************** 007 * Compilation: javac SortCompare.java 008 * Execution: java SortCompare alg1 alg2 N T 009 * 010 * Sort N random real numbers, T times using the two 011 * algorithms specified on the command line. 012 * 013 * % java SortCompare Insertion Selection 1000 100 014 * For 1000 random Doubles 015 * Insertion is 1.7 times faster than Selection 016 * 017 *************************************************************************/ 018 019public class XSortCompare { 020 021 public static double time(String alg, Double[] a) { 022 Stopwatch sw = new Stopwatch(); 023 if (alg.equals("Insertion")) Insertion.sort(a); 024 if (alg.equals("InsertionX")) XInsertionX.sort(a); 025 if (alg.equals("Selection")) Selection.sort(a); 026 if (alg.equals("Shell")) Shell.sort(a); 027 if (alg.equals("Merge")) Merge.sort(a); 028 if (alg.equals("MergeX")) XMergeX.sort(a); 029 if (alg.equals("MergeBU")) MergeBU.sort(a); 030 if (alg.equals("Quick")) Quick.sort(a); 031 if (alg.equals("Quick3way")) Quick3way.sort(a); 032 if (alg.equals("QuickX")) XQuickX.sort(a); 033 if (alg.equals("Heap")) Heap.sort(a); 034 return sw.elapsedTime(); 035 } 036 037 // Use alg to sort T random arrays of length N. 038 public static double timeRandomInput(String alg, int N, int T) { 039 double total = 0.0; 040 Double[] a = new Double[N]; 041 // Perform one experiment (generate and sort an array). 042 for (int t = 0; t < T; t++) { 043 for (int i = 0; i < N; i++) 044 a[i] = StdRandom.uniform(); 045 total += time(alg, a); 046 } 047 return total; 048 } 049 050 public static void main(String[] args) { 051 args = new String[] { "InsertionX", "Insertion", "10000", "20" }; 052 String alg1 = args[0]; 053 String alg2 = args[1]; 054 int N = Integer.parseInt(args[2]); 055 int T = Integer.parseInt(args[3]); 056 double time1 = timeRandomInput(alg1, N, T); // Total for alg1. 057 double time2 = timeRandomInput(alg2, N, T); // Total for alg2. 058 StdOut.format("For %d random Doubles\n %s is", N, alg1); 059 StdOut.format(" %.2f times faster than %s\n", time2/time1, alg2); 060 } 061}