#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;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxtYXRoLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KCgppbnQgbWluKGludCBhLCBpbnQgYil7CglyZXR1cm4gYSA+IGIgPyBiIDogYTsKfQoKLy8gRnVuw6fDo28gZGUgY29tcGFyYcOnw6NvIHVzYWRhIHBlbG8gcXNvcnQgCmludCBjbXBmdW5jIChjb25zdCB2b2lkICogYSwgY29uc3Qgdm9pZCAqIGIpCnsKICBpZiAoKihkb3VibGUqKWEgPiAqKGRvdWJsZSopYikKICAgIHJldHVybiAxOwogIGVsc2UgaWYgKCooZG91YmxlKilhIDwgKihkb3VibGUqKWIpCiAgICByZXR1cm4gLTE7CiAgZWxzZQogICAgcmV0dXJuIDA7ICAKfSAKCi8vIENhbGN1bGEgYSBtZWRpYW5hIGRlIHVtIHZldG9yIGRlIHRhbWFuaG8gPD0gNSBlbSBPKDEpCmRvdWJsZSBmaW5kTWVkaWFuKGRvdWJsZSB2ZWNbXSwgaW50IG4pewogICAgZG91YmxlIG1lZGlhbjsKICAgIC8vIG9yZGVuYcOnw6NvIGNvbSBRdWlja1NvcnQKCXFzb3J0KHZlYywgbiwgc2l6ZW9mKGRvdWJsZSksIGNtcGZ1bmMpOwogICAgbWVkaWFuID0gdmVjWyhuLzIpXTsKICAgIHJldHVybiBtZWRpYW47Cn0KCi8vIEVuY29udHJhIGEgbWVkaWFuYSBhcHJveGltYWRhIGRvIHZldG9yIGVtIE8obikKZG91YmxlIGZpbmRNZWRpYW5PZk1lZGlhbnMoZG91YmxlIHZlY1tdLCBpbnQgbil7CglpbnQgc2l6ZU1lZGlhbnMgPSBjZWlsKG4vNS4wKTsKICAgIGRvdWJsZSBtZWRpYW5zW3NpemVNZWRpYW5zXTsgCgogICAgaWYobiA9PSAwKSByZXR1cm4gMC4wOwogICAgaWYobiA9PSAxKSByZXR1cm4gdmVjWzBdOwogICAgaWYobiA9PSAyKSByZXR1cm4gKHZlY1swXSArIHZlY1sxXSkvMjsKCiAgICBpbnQgY291bnQgPSAwOwogICAgaW50IGNvdW50TWVkaWFucyA9IDA7CiAgICB3aGlsZSAoY291bnQgPCBuKSB7ICAgIAogICAgICAgIGludCBjb3VudFJvdyA9IDA7CiAgICAgICAgaW50IHNpemUgPSBtaW4oNSwgbiAtIGNvdW50KTsKICAgICAgICBkb3VibGUgcm93W3NpemVdOwoKICAgICAgICB3aGlsZSAoKGNvdW50Um93IDwgNSkgJiYgKGNvdW50IDwgbikpIHsKICAgICAgICAgICAgcm93W2NvdW50Um93XSA9ICh2ZWNbY291bnRdKTsKICAgICAgICAgICAgY291bnQrKzsKICAgICAgICAgICAgY291bnRSb3crKzsKICAgICAgICB9CgogICAgICAgIGRvdWJsZSBtID0gZmluZE1lZGlhbihyb3csIHNpemUpOwogICAgICAgIG1lZGlhbnNbY291bnRNZWRpYW5zKytdID0gbTsKICAgIH0KCiAgICByZXR1cm4gZmluZE1lZGlhbk9mTWVkaWFucyhtZWRpYW5zLCBzaXplTWVkaWFucyk7Cn0KCmludCBtYWluKHZvaWQpIHsKCQoJLy9DYWxjdWxhciBhIG1lZGlhbmEgYXByb3hpbWFkYSBkbyB2ZXRvciBhIHNlZ3Vpci4gCgkvL08gYWxnb3JpdG1vIG5lbSBzZW1wcmUgZW5jb250cmEgYSBleGF0YSwgbWFzIGVuY29udHJhIHVtIHZhbG9yIHByw7N4aW1vIChvIHF1ZSBqw6Egw6kgc3VmaWNpZW50ZSkKCWRvdWJsZSB2ZWNbXSA9IHsxNC4xLCAyMi4yLCA3LjMsIDkuNywgMTAuNSwgMTMuMCwgMjEuMn07CgkKCXByaW50ZigiTWVkaWFuOiAlLjJsZlxuIiwgZmluZE1lZGlhbk9mTWVkaWFucyh2ZWMsIDcpKTsKCQoJcmV0dXJuIDA7Cn0K