import java.io.*;
import javax.swing.*;
import java.util.*;
import java.text.DecimalFormat;

public class Sorts
{
  static int SIZE;                          // size of array to be sorted
  static final int MAX_SIZE = 100000;       // maximum allowable size of array to be sorted
  static int[] initValues = new int[MAX_SIZE];  // values to be sorted
  static int[] values = new int[MAX_SIZE];  // values to be sorted

// performance issues if this array is allocated dynamically each time
  static int[] tempArray = new int [MAX_SIZE]; // temporary array used in Merge Sort


  static void initValues(int sortSize)
  // initializes the initValues array with random integers from 0 to SIZE*SIZE
  {
    SIZE = sortSize;
    Random rand = new Random();
    int temp;
    for (int index = 0; index < SIZE; index++) {
      temp = Math.abs(rand.nextInt());
      initValues[index] = temp % (SIZE*SIZE);
      }
  }

  static public boolean isSorted()
  // Determines whether the array values is sorted.
  {
    boolean sorted = true;
    for (int index = 0; index < (SIZE - 1); index++)
      if (values[index] > values[index + 1])
        sorted = false;
    return sorted;
  }

  static void copyInitToValues()
  // Determines whether the array values is sorted.
  {
    for (int index = 0; index < SIZE; index++)
       values[index] = initValues[index];
  }

  static public void swap(int index1, int index2)
  // Swaps the integers at locations index1 and index2 of array values 
  // Precondition: index1 and index2 are less than size
  {
    int temp = values[index1];
    values[index1] = values[index2];
    values[index2] = temp;
  }

  static public void printFmtValues()
  // Prints all the values integers
  {
    int value;
    DecimalFormat fmt = new DecimalFormat("000");
    System.out.println("the values array is:");
    for (int index = 0; index < SIZE; index++)
    {
      value = values[index];
      if (((index + 1) % 10) == 0)
        System.out.println(fmt.format(value));
      else
        System.out.print(fmt.format(value) + " ");
    }
    System.out.println();
  }

  static public void printValues()
  // Prints all the values integers
  {
    int value;
    System.out.println("the values array is:");
    for (int index = 0; index < SIZE; index++)
    {
      value = values[index];
      if (((index + 1) % 10) == 0)
        System.out.println(value);
      else
        System.out.print(value + " ");
    }
    System.out.println();
  }

  static public void printFirstAndLastTenValues()
  // Prints all the values integers
  {
    int value;

    System.out.println("the first 10 in values array are:");
    for (int index = 0; index < 8; index++)
    {
      System.out.print(values[index] + " ");
    }
    System.out.println(values[9]);

    System.out.println("the last 10 in values array are:");
    for (int index = SIZE-10; index < SIZE-2; index++)
    {
      System.out.print(values[index] + " ");
    }
    System.out.println(values[SIZE-1]);

    System.out.println();
  }

  /////////////////////////////////////////////////////////////////
  //  Selection Sort
  //
  public static void selectionSort() {

  }
  /////////////////////////////////////////////////////////////////
  


  /////////////////////////////////////////////////////////////////
  //
  //  Main

  public static void main(String[] args) throws IOException 
  {
    long startTime;
    long sortTime;
    long stopTime;
    long copyTime;

    int i;
    int sortSize, sortIter;

    String inputFileName = JOptionPane.showInputDialog("Enter the input file name");
    String outputFileName = JOptionPane.showInputDialog("Enter the output file name");

    BufferedReader inputFile= new BufferedReader(new FileReader(inputFileName));
    PrintWriter outFile= new PrintWriter(new FileWriter(outputFileName));

    String inLine;
    StringTokenizer tokenizer;

    inLine = inputFile.readLine();

    while (inLine !=null) {
      tokenizer = new StringTokenizer(inLine);
      sortSize = Integer.parseInt( tokenizer.nextToken() );
      sortIter = Integer.parseInt( tokenizer.nextToken() );

      initValues(sortSize);


      // Selection SORT
      copyInitToValues();
      System.out.println("values is sorted: " + isSorted());
      printFirstAndLastTenValues();
      startTime = System.currentTimeMillis();
      for (i = 1 ; i <= sortIter ; i++) {
        copyInitToValues();
        selectionSort();
      }
      sortTime = System.currentTimeMillis()-startTime;
      System.out.println("values is sorted: " + isSorted());
      printFirstAndLastTenValues();
      startTime = System.currentTimeMillis();
      for (i = 1 ; i <= sortIter ; i++) {
        copyInitToValues();
      }
      copyTime = System.currentTimeMillis()-startTime;
      System.out.println("Elapsed time = " + sortTime + " Copy time = "+copyTime);
      System.out.println();
      outFile.println(" Insertion Sort:    size= "+sortSize+"   time= " + (sortTime-copyTime) + " msecs   Iterations= "+sortIter);

      inLine = inputFile.readLine();
    }

      inputFile.close();
      outFile.close();
  }
}