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", "8000", "5" };
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(" %.1f times faster than %s\n", time2/time1, alg2);
060                time1 = timeRandomInput(alg1, N, T); // Total for alg1.
061                time2 = timeRandomInput(alg2, N, T); // Total for alg2.
062                StdOut.format("For %d random Doubles\n    %s is", N, alg1);
063                StdOut.format(" %.1f times faster than %s\n", time2/time1, alg2);
064        }
065}