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

using namespace std; //introduces namespace std



const int MAXSIZE = 5000;
int GetElement();
int Partition(int a[], int m, int p, int &count);
inline void Swap(int  a[], int i, int j);
int  RandomQuickSort(int  a[], int p, int q, int &count);
void PrintResult(int a[]);

//Function to fill array by using random generator

int GetElement(){
int a[MAXSIZE];
for(int  n = 0; n < MAXSIZE; n++){
 a[n] = rand()%5000 + 1;
return a[n];
  }
}

//Function to partition the array of n elements into
//subarray.

int Partition(int  a[], int m , int p, int &count){
int  v = a[m];
int i = m;
int  j = p;
 do{
 do {
count++;
 i++;
}while (a[i] < v);
do{ 
j--;
count++;
}while ( a[j] > v);
if ( i < j)
Swap(a, i ,j);
}while (i < j);
a[m] = a[j];
a[j] = v;
return(j);
}

//Function Swap()

inline void Swap(int  a[], int i, int j){
int  p = a[i];
a[i] = a[j];
a[j] = p;
}


//Funtion RandomQuickSort to sort the array of n elements.
//While sorting the array a[p:q], pick a random element
//from a[p] to a[q] as partition element. Moreover, if 
//there is few elements to sort,the time taken  by the 
//randomizer may be comparable to the rest of the 
//computation. Therefore, the condition is ((q -p)> 5)used
//in the RandomQuickSort function.

int RandomQuickSort(int  a[], int p, int q, int &count){
  if (p < q){
if ((q -p) > 5)
Swap(a, rand()%(q -p +1) + p, p);
int j = Partition(a, p, q + 1, count);
  count = RandomQuickSort(a, p , j -1, count);
  count = RandomQuickSort(a, j +1 , q, count);

  }
  return count ;
}

//Funtion to print kth quantiles of 5000 keys.
//In this test, the values of k is chosen as 200.
void PrintResult(int a[]){
  for(int m = 1 ; m < MAXSIZE; m += 200){
  cout << a[m] << endl;
  }
  

}


int main (){
 int a[MAXSIZE] ;
 int i = 0;
 
 while( i < MAXSIZE){
a[i++]  = GetElement();
}
//Print out only 50 values generated by 
//random generator. If needed tp print
//5000 values, just replace 50 by 5000
//in for loop.
for (int j = 0; j < 50; j++){
cout << a[i++] << endl;
}
int count = 0;
int nComparisons =  RandomQuickSort(a,0, 5000 , count ) ;

cout << "Here is  k:" << ' ' << 200 <<  endl;
cout << "Numbers to form a set of 200 quantiles:" << endl;
PrintResult(a);
cout << "Here is Number of comparisons :" 
     << nComparisons << endl;
return 0;
}