import java.util.*;
import java.text.*;


/**
    This class is used to test Assignment 4, CS 146, Fall 2002
*/

public class A4 {


  /**
      Converts an integer to a string of length 7
      @param the integer
      @return the string
  */
  public static String formatterEZ(int n)                       {
    String BLANKS = "       ";   // 7 blanks
    String s = BLANKS + n;
    return s.substring(s.length()-7);                           }


  /**
       Prints a 2-character string depending whose
       value depends on whether an array (1) is sorted
       and (2) equals a second array.  The first
       character is an "X" if the array is sorted,
       otherwise it is a blank.  The second character
       is an "X" if the two arrays are equal, and a
       blank otherwise
       @param output the first array
       @param insortoutput the second array
  */
  public static void checkSortedness(int[] output,
                                     int[] insortoutput)        {
    if (isSorted(output))
      System.out.print(" ");
    else
      System.out.print("X");
    if (equals(output,insortoutput))
      System.out.print(" ");
    else
      System.out.print("X");                                    }


  /**
      Compares two arrays of integers for equality
      @param a the first array
      @param b the second array
      @return <code>true</code> iff the two arrays
       have the same length, and all elements in
       corresponding positions of the two arrays
       are equal as integers.
   */
  public static boolean equals(int[] a, int[] b)                {
    if (a.length != b.length)
      return false;
    for (int i=0; i<a.length; i++)
      if (a[i] != b[i])
        return false;
    return true;                                                }


  /**
      Determines whether an array of integers is sorted
      in nondecreasing order.
      @param a the array
      @return <code>true</code> iff the array is sorted
  */
  public static boolean isSorted(int[] a)                       {
    int size = a.length;
    for (int i=0; i<size-1; i++)
      if (a[i] > a[i+1])
        return false;
    return true;                                                }


  /**
      Sorts an array of integers using insertion sort.  Mutates
      the input array to contain the sorted sequence.  Also
      maintains a count of the number of element comparisons.
      @param a the array of integers
      @param cc the comparator that maintains the count, and
        is also used for comparing the array elements.
  */
  // This is the insertion sort algorithm of Weiss, p 226, with
  //   the CountingComparator argument added, and the <code>for</code>
  //   loop replaced by a <code>while</code> loop to be consistent
  //   with department coding standards

  public static void insertionSort(int[] a, CountingComparator cc)  {
    for (int p=1; p<a.length; p++)                         {
      int temp = a[p];
      int j=p;
      while (j>0 && cc.compare(a[j-1],temp) > 0)    {
        a[j]=a[j-1];
        j--;                                        }
      a[j] = temp;                                         }        }


  /**
       Applies insertion sort and several variants of quicksort
       to an array of integers, and prints the number of comparisons used
       by each.  Flags (by printing an "X") any case where an algorithm
       returns an unsorted array, or an array different than the one
       returned by insertion sort.  A flag for the first type of
       error appears in the column immediately after the comparison
       count; the flag for the second type of error appears in the
       next column.
       @param a the array to be sorted
       @param cc an object that makes and counts the comparisons
  */

  public static void testAllAlgorithms(int a[], CountingComparator cc)  {
    QSort qs = new QSort();

    int[] acopy = (int[]) a.clone();
    insertionSort(acopy,cc);
    int[] output = (int[]) acopy.clone();
    System.out.print(formatterEZ(cc.getCounter()));
    checkSortedness(acopy, output);
    cc.reset();

    acopy = (int[]) a.clone();
    qs.quicksortNaive(acopy,cc);
    System.out.print(formatterEZ(cc.getCounter()));
    checkSortedness(acopy, output);
    cc.reset();

    acopy = (int[]) a.clone();
    qs.quicksortWeiss(acopy,cc);
    System.out.print(formatterEZ(cc.getCounter()));
    checkSortedness(acopy, output);
    cc.reset();

    acopy = (int[]) a.clone();
    qs.quicksortRandomNaive(acopy,cc);
    System.out.print(formatterEZ(cc.getCounter()));
    checkSortedness(acopy, output);
    cc.reset();

    acopy = (int[]) a.clone();
    qs.quicksortRandomWeiss(acopy,cc);
    System.out.print(formatterEZ(cc.getCounter()));
    checkSortedness(acopy, output);
    cc.reset();

    System.out.println();                                      }


   /**
       Creates various arrays of integers and tests sorting
        algorithms on them, while counting the number of
        comparisons they use.
       @param cc the comparator that maintains the count, and
        is also used for comparing the array elements.
   */

public static void test(CountingComparator cc)                          {
  int asize = 300;
  int[] a = new int[300];
  Random r = new Random(1);
  System.out.println();
  System.out.println();
  System.out.print("                             number of element");
  System.out.println(" comparisons made ");
  System.out.println();
  System.out.print(" algorithm              insertion      --------- ");
  System.out.println("quicksort -------");
  System.out.print("                           sort      unrandomized");
  System.out.println("      randomized");
  System.out.print("                                    naive   Weiss");
  System.out.println("     naive   Weiss");
  System.out.println();

  System.out.print("random input            "     );
  for (int i=0; i<=asize-1; i++)
      a[i]=r.nextInt(10000);
  testAllAlgorithms(a,cc);

  System.out.print("random input 2          "     );
  for (int i=0; i<=asize-1; i++)
      a[i]=r.nextInt(10000);
  testAllAlgorithms(a,cc);

  System.out.print("largely sorted input    "     );
  for (int i=0; i<=asize-1; i++)
    a[i]=r.nextInt(10*i+2);
  testAllAlgorithms(a,cc);

  System.out.print("sorted input            "     );
  for (int i=0; i<=asize-1; i++)
    a[i]=2*i;
  testAllAlgorithms(a,cc);

  System.out.print("reverse sorted input    "     );
  for (int i=0; i<=asize-1; i++)
    a[i]=2*(asize-i);
  testAllAlgorithms(a,cc);

  System.out.print("constant input sequence "     );
  for (int i=0; i<=asize-1; i++)
    a[i]=999;
  testAllAlgorithms(a,cc);                                                }


    /**
        Creates various arrays of integers and tests sorting
        algorithms on them
        @param args is ignored
    */

public static void main(String args[])                         {
  CountingComparator cc = new CountingComparator();
//  test(cc);
//  cc.enableOptionalCounting();
//  System.out.println();
//  System.out.println();
  test(cc);                                                    }


  }