//Electronic copy mailed to nikhil@ccs.neu.edu
//REVISED VERSION
//The algorithm is exactly the same. In the older copy of this program,
//I accidentally left in some incorrect "counter++" lines.
//This made my scores artificially high. Please grade this version.
//I talked to Raj about this on 2/18 and he told me to resubmit the
program.
//Thanks, Steve

//Stephen Wood
//COM1390 Analysis of Algorithms
//Team members: Stephen Wood
//Program notes: I was able to get this to work by typing

//g++ program.cpp
//cat input.txt | a.out

//Where input.txt is the file with the 5000 numbers and the number k

#include <iostream.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>

//The global variables: Array is the place where the 5000 numbers and k
are stored
//Counter keeps track of how many comparisons take place

int Array[5002];
int counter;

//Function Prototypes

int Random(int low, int high);
void Input(void);
void Find(int p, int q, int r, int delta);
int Partition(int p, int q);

//Random Function- Returns a random number between high and low
//Taken from The Art and Science of C, Eric S. Roberts, Page 274
//This function makes the rest of the program easier to write.

int Random(int low, int high)
{
int k;
double d;
d=(double) rand() / ((double) INT_MAX);
k=(int) (d*(high-low+1));
return(low+k);
}

//Input Function
//Reads the list of integers from standard input into Array[1] to
Array[5000]
//Array[5001] holds the value of k (the number of quantiles)
//Array[0] is unused.

void Input(void)
{
int i;
for (i=1;i<5001;i++)
        cin >> Array[i];
cin >> Array[5001];
}

//Partition Function
//Divides the list into two pieces and returns the rank of the pivot
//This is the Randomized Partitioning function from the book.
//Improving this function would increase the algorithm's performance...

int Partition(int p, int q)
{
int i;
int j;
int x;
int temp;
x=Array[Random(p,q)];
i=p;
j=q;
while (1)
        {while (Array[j]>x)
                {j--; counter++;}
         while (Array[i]<x)
                {i++; counter++;}
         if (i<j)
                {temp=Array[i]; 
                Array[i]=Array[j]; 
                Array[j]=temp;}
         else return j;
         }
         }

//Find Function
//Finds the element with rank r and recursively finds elements with rank
r+delta

void Find(int p, int q, int r, int delta)
{
int o;
int z;

o=Partition(p,q);

//If the pivot point = r, return r and recursively find the next quantile.
//If the pivot point < r, recursively find r in the left half and the next
qualntile
//in the right half
//If the pivot point > r, recursively find r in the right half and throw
the left half out

if (r==o)
        {cout << Array[r] << endl;
        z=r+delta;
        if ((z<=q) && !(z==5000)) Find(o+1,q,z,delta);}
else if (r<o)
        {Find(p,o-1,r,delta);
        z=r;
        while (z<o) z=z+delta;
        if ((z<=q) && !(z==5000)) Find(o,q,z,delta);}
else Find(o+1,q,r,delta);
}

//Main function
//Load the values from standard input, find the first quantile (r) and the
distance
//to the next quantile (delta)
//Use these values to call Find, then report the counter total at the end!

int main(void)
{
srand (time(NULL));
counter=0;
Input();
Find(1,5000, (5000/Array[5001]),(5000/Array[5001]));
cout << counter << endl;
return(0);
}