fork(1) download
  1. #include <stdio.h>
  2. #include <math.h>
  3. #include <stdlib.h>
  4.  
  5.  
  6. int min(int a, int b){
  7. return a > b ? b : a;
  8. }
  9.  
  10. // Função de comparação usada pelo qsort
  11. int cmpfunc (const void * a, const void * b)
  12. {
  13. if (*(double*)a > *(double*)b)
  14. return 1;
  15. else if (*(double*)a < *(double*)b)
  16. return -1;
  17. else
  18. return 0;
  19. }
  20.  
  21. // Calcula a mediana de um vetor de tamanho <= 5 em O(1)
  22. double findMedian(double vec[], int n){
  23. double median;
  24. // ordenação com QuickSort
  25. qsort(vec, n, sizeof(double), cmpfunc);
  26. median = vec[(n/2)];
  27. return median;
  28. }
  29.  
  30. // Encontra a mediana aproximada do vetor em O(n)
  31. double findMedianOfMedians(double vec[], int n){
  32. int sizeMedians = ceil(n/5.0);
  33. double medians[sizeMedians];
  34.  
  35. if(n == 0) return 0.0;
  36. if(n == 1) return vec[0];
  37. if(n == 2) return (vec[0] + vec[1])/2;
  38.  
  39. int count = 0;
  40. int countMedians = 0;
  41. while (count < n) {
  42. int countRow = 0;
  43. int size = min(5, n - count);
  44. double row[size];
  45.  
  46. while ((countRow < 5) && (count < n)) {
  47. row[countRow] = (vec[count]);
  48. count++;
  49. countRow++;
  50. }
  51.  
  52. double m = findMedian(row, size);
  53. medians[countMedians++] = m;
  54. }
  55.  
  56. return findMedianOfMedians(medians, sizeMedians);
  57. }
  58.  
  59. int main(void) {
  60.  
  61. //Calcular a mediana aproximada do vetor a seguir.
  62. //O algoritmo nem sempre encontra a exata, mas encontra um valor próximo (o que já é suficiente)
  63. double vec[] = {14.1, 22.2, 7.3, 9.7, 10.5, 13.0, 21.2};
  64.  
  65. printf("Median: %.2lf\n", findMedianOfMedians(vec, 7));
  66.  
  67. return 0;
  68. }
  69.  
Success #stdin #stdout 0s 9424KB
stdin
Standard input is empty
stdout
Median: 15.85