#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[] = {14.1, 22.2, 7.3, 9.7, 10.5, 13.0, 21.2};
	
	printf("Median: %.2lf\n", findMedianOfMedians(vec, 7));
	
	return 0;
}
