// Beth L. Riedel
// COM1390 - Assignment #1
// February 16, 1999
// Comments - This program does not determine the fewest number of comparisons
//            when finding the quantiles.  I attempted a number of different
//            sorting algorithms and techniques of my own but could not get
//            any of them to work.  I could not figure out a way to determine
//            the quantiles without sorting the list first.  Although this 
//            program is not efficient, it is correct and clear.
//
// --------------------------------------------------
import java.io.*;
import java.lang.*;
import java.util.*;

class Quantiles {

  // file name should be passed through program execution

  public static void main (String[] args)
       throws IOException
  {
    final int n = 5000;
    InputStream fin = new FileInputStream(args[0]); 
    DataInputStream in = new DataInputStream(fin);
    int[] myArray = new int[n];
    int[] sortedArray = new int[n];
    for (int i = 0; i < n; i++) {               // read the list of integers
      String line = in.readLine();              // from the file into an array
      myArray[i] = Integer.parseInt(line, 10);
    }
    String line = in.readLine();         // last line of file is the 
    int k = Integer.parseInt(line, 10);  // kth quantiles to be found
    in.close();                          // close file
    doSortArray(myArray, n, k);          // sort array
  }

  public static void doSortArray (int[] A, int n, int k) {
    
    // insertion sort - worst-case is O(n^2)

    int count = 0;
    
    for (int j = 2; j < n; j++) {
      int key = A[j];
      int i = j - 1;
      while ((i >= 0) && (A[i] > key)) {
	count++;
	A[i+1] = A[i];
	i = i - 1;
      }
      A[i+1] = key;
    }
    System.out.println("The number of comparisons performed when sorting the list of integers is:  " + count);
    determineQuantiles(A, n, k);
  }
  
  public static void determineQuantiles (int[] sortedArray, int n, int k) {

    int quantCount = 0;
    int key = n/k;
    int keyInc = key;
    
    // Given - n is a multiple of k
    //         We need to determine (k-1) elements that divide the list
    //         into k sets of (n/k) elements each, to within 1.
    //         We know the quantiles will be at most (n/k) elements apart and
    //         we know we only need (k-1) elements to form the kth quantiles.
    //         An increment and a counter has been used to determine the 
    //         kth quantiles.

    System.out.println("The following elements form the " + k + "th quantiles:"); 
    while ((key <= n) && (quantCount < (k - 1))) {
      System.out.println(sortedArray[key]);
      key = key + keyInc;
      quantCount ++;
    }
    System.out.println("The number of comparisons performed when determining the quantiles is:  " + quantCount);
  }
}