/* Programming Assignment 1 for COM 1390 by Gregory Clem
   (Creation and completion: 2/8/99-2/12/99)
   This program, given an list of 5000 elements and a k
   returns the elements that divid the k quantiles of the list
   and returns the number of element comparisons required to
   reach that conclusion. There will be no output beyond the numbers.
   The expected runtime is Theta(nlgn). */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

const n=5000;

// Must have n integers in the array.
int nlist[5000];
int it, k, r;
int p = 0;
int compare = 0;


/* The Random Integer function was taken from the book 
   'The Art and Science of C' by Eric S. Roberts. Copyright 1995. p 694.
   Picks a random number that is equal to low, high or in between. */

int RandomInteger(int low, int high)
{
 int k;
 double two;
 two = (double) rand() / ((double) RAND_MAX + 1);
 k = (int) (two * (high-low+1));
 return (low+k);
}


/* Gets the input of the elements (currently set to 5000 as the problem
   states) and K. It is assumed the correct information as stated in
   the assignment will be placed in the input so deviation is not checked
   for speed purposes. */

void GetInput(int Ary[], int& kth)
{
 int repeat;
 for (repeat=0; repeat < n; repeat++) {

// Takes in the elements, one at a time.
        scanf("%d", &Ary[repeat]);
        }

// Takes in an interger input for k.
 scanf("%d", &kth);
}


/* Partitions the array between pp and pr around the number in pr.
   Lower numbers go on one side, greater numbers on the other. It
   returns the location of the number that seperates the halves. */

int Partition(int A[], int pp, int pr, int& pcount)
{
 int x, i, j, temp;

// x gets the last number in the section as marked by pr
 x = A[pr];

// i gets one below the first point.
 i = pp-1;
 for (j=pp; j < pr; j++) {

// If the element is less then the what x is, switch A[i] and A[j]
        if (A[j] < x) {
		i++;

// Does the switch
		temp=A[i];
		A[i]=A[j];
		A[j]=temp;
		}

// Counts the element comparison for the total at the end.
        pcount++;
	}

// Switches nlist[i+1] and nlist[pr]
 temp=nlist[i+1];
 nlist[i+1]=nlist[pr];
 nlist[pr]=temp;

// Returns the dividing point, which the array is partitioned around.
 return(i+1);
}


/* The altered version of quicksort where expected time is O(nlgn)
   even if the array is sorted. */

void RandomizedQuicksort(int S[], int rp, int rr, int& rcount)
{
 int y, q, q1, temp;

// A comparison that only checks positions to see if the section has more
// then one element. It does not compare actual elements.
 if (rp < rr) {

// Gets a random number inclusively between rp and rr.
	y= RandomInteger(rp,rr);

// Switches S[y] and S[rr] so Partition becomes more random
// and will not default to the worst case in a sorted list.
        temp=S[y];
        S[y]=S[rr];
        S[rr]=temp;

// Retrieves the position that the array section, that will be seperated
// into to smaller arrays, on either side of it.
        q = Partition(S,rp,rr, rcount);
	q1=q+1;

// Recursive call on the first section.
        RandomizedQuicksort(S, rp, q, rcount);

// Recursive call on the second section.
        RandomizedQuicksort(S, q1, rr, rcount);
        }
}
 

/* Computes the k-1 elements that seperate the k quantiles and sends the
   information to output along with the number of comparisons. */

void GiveKQuantiles(int list[], int k, int& gcount)

{
 int i, step, iter;

// Determines how many positions away one quantile divider is from the
// next in the now sorted array. This works because stated in the
// assignment clarification that k will be a number that has n as a
// multiple, so the quantile sizes are uniform.
 step=n/k;
 for (iter=n/k-1 ; iter < n-1; iter=iter+step) {

// Iterates by the step to stop at each quantile and output it.
	printf("%d\n",list[iter]);
	}

// Prints the number of element comparisons made in the program.
 printf("%d\n",gcount);
}

       
/* Calls the procedures that make up each step of the program;
   Input, Computation and Determination, and Output. */

main()
{

// sets r to mark the end of the list.
 r = n-1;
 GetInput(nlist,k);
 RandomizedQuicksort(nlist,p,r,compare);
 GiveKQuantiles(nlist,k,compare);
}