fork download
copy 
  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[] = {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};
  64.  
  65. 	double median = findMedianOfMedians(vec, 45);
  66.  
  67. 	printf("Median: %.2lf\n", median);
  68.  
  69. 	int menoresIguais = 0, maiores = 0;
  70.  
  71. 	for(int i=0; i<45; i++){
  72. 		if(vec[i] < median){
  73. 			menoresIguais++;
  74. 		} else{
  75. 			maiores++;	
  76. 		}
  77. 	}
  78.  
  79. 	printf("Quantidade de menores ou iguals que a mediana: %d.\nQuantidade de maiores que a mediana: %d.\n", menoresIguais, maiores);
  80.  
  81. 	return 0;
  82. }
  83.  
Success #stdin #stdout 0s 9424KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
Median: 12148.50
Quantidade de menores ou iguals que a mediana: 27.
Quantidade de maiores que a mediana: 18.
https://ideone.com/lXOWSd
language:
C (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!