package algorithms.elementary21;

 /******************************************************************************

  *  Compilation:  javac SortCompare.java

  *  Execution:    java SortCompare alg1 alg2 N T

  *  Dependencies: StdOut.java Stopwatch.java

  *

  *  Sort N random real numbers, T 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;

 import algorithms.analysis14.Stopwatch;

 import algorithms.util.StdOut;

 import algorithms.util.StdRandom;

 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 T random arrays of length N.

     public static double timeRandomInput(String alg, int N, int T)  {

         double total = 0.0;

         Double[] a = new Double[N];

         // Perform one experiment (generate and sort an array).

         for (int t = 0; t < T; t++) {

             for (int i = 0; i < N; i++)

                 a[i] = StdRandom.uniform();

             total += time(alg, a);

         }

         return total;

     } 

     // Use alg to sort T random arrays of length N.

     public static double timeSortedInput(String alg, int N, int T)  {

         double total = 0.0;

         Double[] a = new Double[N];

         // Perform one experiment (generate and sort an array).

         for (int t = 0; t < T; 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 T = Integer.parseInt(args[3]);

         double time1, time2;

         if (args.length == 5 && args[4].equals("sorted")) {

             time1 = timeSortedInput(alg1, N, T); // Total for alg1.

             time2 = timeSortedInput(alg2, N, T); // Total for alg2.

         }

         else {

             time1 = timeRandomInput(alg1, N, T); // Total for alg1.

             time2 = timeRandomInput(alg2, N, T); // Total for alg2.

         }

         StdOut.printf("For %d random Doubles\n    %s is", N, alg1);

         StdOut.printf(" %.1f times faster than %s\n", time2/time1, alg2);

     }

 } 

 package algorithms.elementary21;

 import algorithms.util.StdDraw;

 import algorithms.util.StdRandom;

 /******************************************************************************

  *  Compilation:  javac InsertionBars.java

  *  Execution:    java InsertionBars N

  *  Dependencies: StdDraw.java

  *

  *  Insertion sort N random real numbers between 0 and 1, visualizing

  *  the results by ploting bars with heights proportional to the values.

  *

  *  % java InsertionBars 20

  *

  ******************************************************************************/

 public class InsertionBars {

     public static void sort(double[] a) {

         int N = a.length;

         for (int i = 0; i < N; i++) {

             int j = i;

             while (j >= 1 && less(a[j], a[j-1])) {

                 exch(a, j, j-1);

                 j--;

             }

             show(a, i, j);

         }

     }

     private static void show(double[] a, int i, int j) {

         StdDraw.setYscale(-a.length + i + 1, i);

         StdDraw.setPenColor(StdDraw.LIGHT_GRAY);

         for (int k = 0; k < j; k++)

             StdDraw.line(k, 0, k, a[k]*.6);

         StdDraw.setPenColor(StdDraw.BOOK_RED);

         StdDraw.line(j, 0, j, a[j]*.6);

         StdDraw.setPenColor(StdDraw.BLACK);

         for (int k = j+1; k <= i; k++)

             StdDraw.line(k, 0, k, a[k]*.6);

         StdDraw.setPenColor(StdDraw.LIGHT_GRAY);

         for (int k = i+1; k < a.length; k++)

             StdDraw.line(k, 0, k, a[k]*.6);

     }

     private static boolean less(double v, double w) {

         return v < w;

     }

     private static void exch(double[] a, int i, int j) {

         double t = a[i];

         a[i] = a[j];

         a[j] = t;

     }

     public static void main(String[] args) {

         int N = Integer.parseInt(args[0]);

         StdDraw.setCanvasSize(160, 640);

         StdDraw.setXscale(-1, N+1);

         StdDraw.setPenRadius(.006);

         double[] a = new double[N];

         for (int i = 0; i < N; i++)

             a[i] = StdRandom.uniform();

         sort(a);

     }

 }

 package algorithms.elementary21;

 import algorithms.util.StdDraw;

 import algorithms.util.StdRandom;

 /******************************************************************************

  *  Compilation:  javac SelectionBars.java

  *  Execution:    java SelectionBars N

  *  Dependencies: StdDraw.java

  *

  *  Selection sort N random real numbers between 0 and 1, visualizing

  *  the results by ploting bars with heights proportional to the values.

  *

  *  % java SelectionBars 20

  *

  ******************************************************************************/

 public class SelectionBars {

     public static void sort(double[] a) {

         int N = a.length;

         for (int i = 0; i < N; i++) {

             int min = i;

             for (int j = i+1; j < N; j++)

                 if (less(a[j], a[min])) min = j;

             show(a, i, min);

             exch(a, i, min);

         }

     }

     private static void show(double[] a, int i, int min) {

         StdDraw.setYscale(-a.length + i + 1, i);

         StdDraw.setPenColor(StdDraw.LIGHT_GRAY);

         for (int k = 0; k < i; k++)

             StdDraw.line(k, 0, k, a[k]*.6);

         StdDraw.setPenColor(StdDraw.BLACK);

         for (int k = i; k < a.length; k++)

             StdDraw.line(k, 0, k, a[k]*.6);

         StdDraw.setPenColor(StdDraw.BOOK_RED);

         StdDraw.line(min, 0, min, a[min]*.6);

     }

     private static boolean less(double v, double w) {

         return v < w;

     }

     private static void exch(double[] a, int i, int j) {

         double t = a[i];

         a[i] = a[j];

         a[j] = t;

     }

     public static void main(String[] args) {

         int N = Integer.parseInt(args[0]);

         StdDraw.setCanvasSize(260, 640);

         StdDraw.setXscale(-1, N+1);

         StdDraw.setPenRadius(.006);

         double[] a = new double[N];

         for (int i = 0; i < N; i++)

             a[i] = StdRandom.uniform();

         sort(a);

     }

 }