/*
 *  COM 1390
 *  Programming Assignment 1
 *      2/15/1999 
 *
 *      NAME: Masamune Ishikawa
 *    ID: 900 021 692
 *       
 *      Tool: Metrowerks's CodeWarrior for Macintosh
 *
 */

#include <iostream>
#include <fstream.h>
#include <stdlib.h>
                
main()
{       
        const int DATA_SIZE = 5000;             //DATA_SIZE = element of
n.
        int data_array [DATA_SIZE];
        
        ifstream data_file ("test");    //Open the input file called test.
        
        int i, j, t;    // i=for index, j=for swap, t=for temp 
        int count = 0;  // counter
        int kth;
        int in;         // to check integer
        float fl, keys; // to check float
        
                //Check if file is missing
                if (data_file.bad()) {
                        cerr << "Error: Could not open test file. \n";
                        cerr << "Please make a text file called test to
input \n";
                        exit (8);
                        }

        //Read input file into the array (elements and a key)
        for (i = 0; i <= DATA_SIZE; ++i)
                data_file >> data_array[i];
                
        int key = data_array[DATA_SIZE];        //Set Last number as key
        
        
                // Check n is a multiple of k
                keys = key;
                fl = DATA_SIZE/keys;    
                in = DATA_SIZE/keys;
                if (fl != in) {                                 
                        cout << "Please remember n is a multiple of k! \n"
<< '\n';
                        cout << "Your element n is: " << DATA_SIZE <<
'\n';
                        cout << "You choose k as: "<< key << '\n';
                        //cout << "float: "<< fl << '\n';
                        //cout << "Int: "<< in << '\n';
                        exit (8);
                        }
        
        /*      
        //datacheck
        cout << "Key K=:" << key << '\n';
        for (i = 0; i < DATA_SIZE; ++i)
        cout << "Data are: " << data_array[i] << '\n';
        //end
        */      
        
                // Sorting array by insertion sort
                for ( i=0; i < DATA_SIZE; ++i)
                {
                        j=i;            
                        while (j >= 1 && data_array[j-1] > data_array[j]) 
                        {
                                count = count +1;
                                t = data_array[j];
                                data_array[j] = data_array[j-1];
                                data_array[j-1] = t;
                                j--; 
                        }
                }
        
        /*
        //datacheck
        for (i = 0; i < DATA_SIZE; ++i)
        cout << "Sorted: " << data_array[i] << '\n';
        //end           
        */
        
        int k;                  //k = k-1 position
        kth = key;              //kth is for k
        
        cout << key << "th quantiles: "<<'\n';
        for (kth = 1; kth<= key-1; ++kth)
        {
                k = kth*DATA_SIZE/key;  
                //cout << "Kth:" << k << '\n';
                cout << "Divided point:array#"<< k << " =  " <<
data_array[k] << '\n';
        }
        cout << "The number of comparisons:" << count << '\n';
        return (0);
}