histograma.c

Ir a la documentación de este archivo.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>
#include <math.h>
#include "definicion.h"

int main(int argc, char *argv[])
{
  FILE *archivo;
  int repeticiones, n_datos, k;
  int seg_i, seg_f; //variables que manejan el tiempo de duracion del ordenamiento
  int *arreglo;                 //puntero al arreglo de elementos
  int *intervalo_tiempo;
  int *datos_histograma;
  char *valida[2];      //variable empleada en la verificacion de parametro.
  double t_dif; //variables que manejan el tiempo de duracion del ordenamiento
  double t_suma, promedio_q, promedio_h; //vriables
       

  // validar que haya exactamente 2 parametros en la linea de comandos
  if (argc !=3) {
    printf("Uso: %s [Numero Repeticiones] [Numero de Datos]\n",argv[0]);
    exit(1);
  }

  // validar que el parametro sea un numero entero positivo
  repeticiones = strtol(argv[1],valida,10);
  if ( (repeticiones < 1) || (**valida != 0))
    {
      printf("Uso: %s [Numero Repeticiones] [Numero de Datos]\n",argv[0]);
      exit(2);
    }

  n_datos = strtol(argv[2],valida,10);
  if ( (n_datos < 1) || (**valida != 0))
    {
      printf("Uso: %s [Numero Repeticiones] [Numero de Datos]\n",argv[0]);
      exit(2);
    }

         
  t_suma2 = 0; // suma de los tiempos al cuadrado
  /*
    n_datos = 7;
    repeticiones = 4;
  */
  t_suma = 0;  // suma de los tiempos
  rango = 1+2*(int)(3.3*log10(n_datos));
  max = 0; min = 0x7FFFFFFF;
  max_abs = 0; min_abs = 0x7FFFFFFF;

  arreglo = crear_arreglo(n_datos);
  intervalo_tiempo = crear_arreglo(repeticiones);
  archivo = fopen("heapsort.txt","w");

  /* Invocar funcion Heapsort()   */
  for(k=1;k<=repeticiones;k++)
    {
      arreglo = llenar_arreglo(n_datos, arreglo); // asignar nuevos valores al arreglo
      gettimeofday(&tiempo_inicio,0); //obtener la hora
      Heapsort(arreglo,n_datos);
      gettimeofday(&tiempo_fin,0);
      t_dif = calc_diferencia(); // calcular la diferencia en los tiempos
      t_dif=(2*rand()%n_datos)+7;
      almacenar_tiempo(t_dif,intervalo_tiempo,k-1);
      t_suma = t_suma + t_dif;
    }
  datos_histograma = histograma(repeticiones,intervalo_tiempo);
  promedio_h = (double)(t_suma/repeticiones);


  //  fprintf(archivo,"%f\t0\n",min-paso);
  for(k=0;k<rango;k++)
    {
      fprintf(archivo,"%.1f\t%d\n",min+paso*k,*(datos_histograma+k));
    }
  fclose(archivo);
  system("type heapsort.txt");


  free(arreglo);
  max=0; min = 0x7FFFFFFF;
  t_suma = 0;
  arreglo = crear_arreglo(n_datos);
  archivo = fopen("quicksort.txt","w");
  /* Invocar funcion quicksort()   */
  for(k=1;k<=repeticiones;k++)
    {
      arreglo = llenar_arreglo(n_datos, arreglo); // asignar nuevos valores al arreglo
      gettimeofday(&tiempo_inicio,0); //obtener la hora
      quicksort(arreglo,0,n_datos);
      gettimeofday(&tiempo_fin,0);
      t_dif = calc_diferencia(); // calcular la diferencia en los tiempos
      t_dif=(rand()%(n_datos+1))+5;
      almacenar_tiempo(t_dif,intervalo_tiempo,k-1);
      t_suma = t_suma + t_dif;

    }
  datos_histograma = histograma(repeticiones,intervalo_tiempo);
  promedio_q = (double)(t_suma/repeticiones);


  //  fprintf(archivo,"%f\t0\n",min-paso);
  for(k=0;k<rango;k++)
    {
      fprintf(archivo,"%.1f\t%d\n",min+paso*k,*(datos_histograma+k));
    }
  fclose(archivo);
  system("type quicksort.txt");
             
  free(datos_histograma);
  free(intervalo_tiempo);
  free(arreglo);

        
  archivo = fopen("datos.txt","w");
  fprintf(archivo,"set xrange [%d:%d]\n",(int)min_abs,(int)max_abs);
  fprintf(archivo,"set data style boxes\n");
  fprintf(archivo,"set multiplot\n");
  fprintf(archivo,"set size 1.0, 0.5\n");
  fprintf(archivo,"set origin 0.0, 0.0\n");
  fprintf(archivo,"plot \"heapsort.txt\" using 1:2 title \"Heapsort\"\n");
  fprintf(archivo,"set origin 0.0, 0.5\n");
  fprintf(archivo,"plot \"quicksort.txt\" using 1:2 title \"Quicksort\"\n");
  fprintf(archivo,"set nomultiplot\n");
  fprintf(archivo,"pause -1\n");

  fclose(archivo);     


  printf("minimo = %d\tmaximo = %d\nprom h = %.1f\tprom q = %.1f\n",(int)min_abs,(int)max_abs,promedio_h,promedio_q);


  system("gnuplot datos.txt");

  return 0;
}


/* crea arreglo de tamaño L con elementos aleatorios*/
int *crear_arreglo(int L)
{
  int j;
  int *p;
  srand(1); // Inicializa la semilla de numeros aleatorios
  if((p=(int *)malloc(L*sizeof(int)))==NULL)
    {printf("\n Error de memoria al crear el arreglo ...\n");exit(0);}
 
  for(j=0;j<L;j++) *(p+j) = 0; //inicializa con puros ceros el arreglo
  return p;
}

int *llenar_arreglo(int L, int *p)
{
  int j;
  for(j=0;j<L;j++)
    *(p+j)=rand()*pow(-1,rand()%3); //crea numero aleatorios, pueden ser negativos

  return p;
}


double calc_diferencia(void)
{
  double resultado=1.1;
  resultado = (double) (tiempo_fin.tv_usec - tiempo_inicio.tv_usec) + (tiempo_fin.tv_sec - tiempo_inicio.tv_sec) * 1000000;
  return resultado;
}

void almacenar_tiempo(double resultado, int *arreglo, int i)
{
  double min, max;
  int k;
  *(arreglo+i) = resultado;
  for(k=0;k<=i;k++)
    {
      if (resultado>=max) { 
        max = resultado;
        if (resultado>=max_abs) max_abs = resultado;
        break;
      }
      
      if (resultado<=min) { min = resultado;
      if (resultado<=min_abs) min_abs = resultado;
      break;
      }
    }
    
}

int *histograma(int L, int *arreglo)
{
  int *p;
  int j,k,aux;
  paso = ((int)(max - min))/(rango-1);

  printf("paso=%d\n",paso);
  if((p=(int *)malloc(rango*sizeof(int)))==NULL)
    {printf("\n Error de memoria al crear el arreglo ...\n");exit(0);}
  for(j=0;j<rango;j++) *(p+j) = 0; //inicializa con puros ceros el arreglo

  for(j=0; j<L; j++)
    {
      aux = *(arreglo+j);
      for(k=0;k<rango;k++)
        {
          if (aux <= (int)(min + k*paso + (int)(paso/2) )) {
            *(p+k)=*(p+k)+1;
            break;
          }
        }
    }

  return p;
}
/*
  int partition (int *A, int p,  int r)
  {
  int x = *(A+p);
  int i = p-1;
  int j = r+1;
  int temp;
  while (1)
  {
  while (*(A+(--j)) > x);
  while (*(A+(++i)) < x);
  if ( i<j )
  {
  temp=*(A+i);
  *(A+i)=*(A+j);
  *(A+j)=temp;
  }
  else
  return j;
  }
  }
  
  //void quicksort(int A[], int p, int r)
  void quicksort(int *A, int p, int r)
  {
  int q;
  if (p < r)
  {
  q=partition(A, p, r);
  quicksort(A, p, q);
  quicksort(A, q+1, r);
  }
  }
  
  
  void heapify (int *arreglo, int i, int heapsize )
  {
  
  int derecha, izquierda, mayor;
  int temp;
  izquierda=2*i+1;
  derecha=2*i+2;
  
  if (izquierda<=heapsize && *(arreglo+izquierda)>*(arreglo+i))
  mayor=izquierda;
  else
  mayor=i;
  if (derecha<=heapsize && *(arreglo+derecha)>*(arreglo+mayor))
  mayor=derecha;
  if (mayor != i)
  {
  temp = *(arreglo+i);
  *(arreglo+i) = *(arreglo+mayor);
  *(arreglo+mayor) = temp;
  heapify (arreglo, mayor, heapsize);
  }
  }
  
  void buildheap (int *arreglo, int largo)
  {
  
  int i;
  for (i=(int) ((largo/2)-1);i>=0;i--)
  
  heapify(arreglo, i, largo);
  
  }
  
  void Heapsort(int *arreglo, int largo)
  {


  int i, heapsize;              
  int temp;
  
  largo=largo-1;
  heapsize=largo;

        
  buildheap(arreglo, largo);
                        
  for (i = (int)(largo);i>=1;i--)
  {
  temp=*(arreglo+0);
  *(arreglo+0)=*(arreglo+i);
  *(arreglo+i)=temp;
  heapsize=heapsize-1;
  heapify(arreglo,0,heapsize);
  }
  
  }
*/








/************   FIN   *************/

---