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


int min(int a, int b){
	return a > b ? b : a;
}

// Função de comparação usada pelo qsort 
int cmpfunc (const void * a, const void * b)
{
  if (*(double*)a > *(double*)b)
    return 1;
  else if (*(double*)a < *(double*)b)
    return -1;
  else
    return 0;  
} 

// Calcula a mediana de um vetor de tamanho <= 5 em O(1)
double findMedian(double vec[], int n){
    double median;
    // ordenação com QuickSort
	qsort(vec, n, sizeof(double), cmpfunc);
    median = vec[(n/2)];
    return median;
}

// Encontra a mediana aproximada do vetor em O(n)
double findMedianOfMedians(double vec[], int n){
	int sizeMedians = ceil(n/5.0);
    double medians[sizeMedians]; 

    if(n == 0) return 0.0;
    if(n == 1) return vec[0];
    if(n == 2) return (vec[0] + vec[1])/2;

    int count = 0;
    int countMedians = 0;
    while (count < n) {    
        int countRow = 0;
        int size = min(5, n - count);
        double row[size];

        while ((countRow < 5) && (count < n)) {
            row[countRow] = (vec[count]);
            count++;
            countRow++;
        }

        double m = findMedian(row, size);
        medians[countMedians++] = m;
    }

    return findMedianOfMedians(medians, sizeMedians);
}

int main(void) {
	
	//Calcular a mediana aproximada do vetor a seguir. 
	//O algoritmo nem sempre encontra a exata, mas encontra um valor próximo (o que já é suficiente)
	double vec[] = {8615, 11916, 16355, 12755, 15219, 11364, 9739, 13373, 3151, 3500, 8566, 15285, 6617, 16484, 13096, 5947, 11737, 5067, 14165, 3569, 14263, 14288, 2728, 15063, 10913, 3163, 9893, 13660, 3026, 18147, 10743, 8019, 3565, 13810, 10111, 12865, 12077, 3696, 18201, 10430, 11542, 8936, 15773, 7915, 16064};
	
	double median = findMedianOfMedians(vec, 45);
	
	printf("Median: %.2lf\n", median);
	
	int menoresIguais = 0, maiores = 0;
	
	for(int i=0; i<45; i++){
		if(vec[i] < median){
			menoresIguais++;
		} else{
			maiores++;	
		}
	}
	
	printf("Quantidade de menores ou iguals que a mediana: %d.\nQuantidade de maiores que a mediana: %d.\n", menoresIguais, maiores);
	
	return 0;
}