/**
 * COM1390 Algorithms
 * Programming Assignment: Finding Quantiles
 * Name: Ho-Wan Sin
 * ID: 900-02-1893
 */

Public class Quantiles {
public static Element[] elements;
int comparison;
/**
 * Main Program
 */
public static void main {
     elements = new Element [5000]; 
     System.out.print ("Please input number of quantiles => ");
     System.in.read(int k);
     quicksort(elements[], 1, 5000);
     equalsize(elements[], k);
}
/**
 * Element class
 * input 5000 distinct integer
 */
class Element {
     public Element {
         for (int i = 1; i<=5000; i++) {
              System.out.print ("Please input an integer => ")
              elements[i] = new Element (i);
              System.in.read(elements[i]);
              comparison = comparison + 1;
          }
     }
}
/**
 * quicksort class
 * doing the quicksort
 */
class quicksort {
     public quicksort (Element elements, int p, int r) {
         if (p < r) {
             comparison = comparison + 1;
             int q = partition(elements[], p, r);
             quicksort (elements[], p, q);
             quicksort (elements[], q + 1, r);
         }
     }
}
/**
 * partition class
 * doing the partition part in quicksort
 */
class partition {
     public partition (Element elements, int p, int r) {
         int x = elements[p];
         int i = p - 1;
         int j = r + 1;
         while (true) {
               while (elements[j] > x) {
                     comparison = comparison + 1;
                     j = j - 1;}
               while (elements[i] < x) {
                     comparison = comparison + 1;
                     i = i + 1;}
               if (i < j) {
                   comparison = comparison + 1;
                   int temp = elements[i];
                   elements[i] = elements[j];
                   elements[j] = temp;
              } 
              else {
                   return j;
               }
          }
      }
}
/**
 * equalsize class
 * print out resulted quantiles and the number of comparisons
 */
class equalsize {
     private j = 1;
     public equalsize (Element elements, int k) {
          for (int i = 1; i < k; i++) {
               comparison = comparison + 1;
               while (j < i*5000/k) {
                   comparison = comparison + 1;
                   System.out.print (elements[j] + " ");
                   j = j + 1;
               }
               j = j + 1;
               System.out.println (" ");
           }
           for (int i = j; j <= 5000; j++) {
                comparison =  comparison + 1;
                System.out.print (elements[j] + " ");
           }
           System.out.println (" ");
           System.out.println ("The number of comparisons performed by my algorithm is " + comparison);
      }
}
}