P4 CALVORITMOS FINAL (BUSCAR COTAS SAMUEL RATA)

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <sys/time.h>
#include <math.h>
#define TAM 512000
typedef struct {
    int vector[TAM];
    int ultimo;
} monticulo;

double microsegundos() {
    struct timeval t;
    if (gettimeofday(&t, NULL) < 0 )
        return 0.0;
    return (t.tv_usec + t.tv_sec * 1000000.0);
}

void Hundir(monticulo *m, int i){
    int aux;
    int j=i;
    int HijoIzq;
    int HijoDer;
    while(j!=i) {
        HijoIzq=2*i+1;
        HijoDer=2*i+2;
        if (HijoDer <= TAM && m->vector[HijoDer] > m->vector[i]) {
            i = HijoDer;
        }
        if (HijoIzq <= TAM && m->vector[HijoIzq] > m->vector[i]) {
            i = HijoIzq;
        }
        aux = m->vector[j];
        m->vector[j] = m->vector[i];
        m->vector[i] = aux;
    }

}

void ascendente(int v [], int n) {
    int i;
    for (i=0; i < n; i++)
        v[i] = i;
}

void descendente(int v [], int n){
    int i;
    int j;
    for (i=0; i < n; i++) {
        j = 10 - i;
        v[i] = j;
    }
}

void aleatorio(int v [], int n) {/* se generan números pseudoaleatorio entre -n y +n */
    int i, m=2*n+1;
    for (i=0; i < n; i++)
        v[i] = (rand() % m) - n;
}


void crear_monticulo(int a[], int b, monticulo *m){
    int i;
    int j;
    m->ultimo=b;
    for(j=0;a[j-1]!=b;j++){//REVISAR
        m->vector[j]=a[j];
    }
    for (i = TAM; i >= 0; i--) {
      Hundir(m, i);
    }
}

int eliminar_mayor(monticulo *m){
    if(m->vector[2] > m->vector[1]){
        m->vector[0]=m->vector[2];
    }if(m->vector[2] < m->vector[1]){
        m->vector[0]=m->vector[1];
    }
    Hundir(m,0);
    return m->vector[0];
}

void ord_monticulo(int V[], int n){
    int i;
    monticulo *M = malloc(sizeof(monticulo));
    crear_monticulo(V,V[n],M);
    for(i=n;i>=1;i--){
        V[i]= eliminar_mayor(M);
    }
    free(M);
}

void imprimirAscendente(int vector[]){
    int i,k;
    double t,ta,tb,t1,t2;

    printf("ASCENDENTE\n");
    printf("n         t\n");

    for(i=500;i<=32000;i=i*2) {
        ascendente(vector, i);
        ta=microsegundos();
        ord_monticulo(vector,i);
        tb=microsegundos();
        t=tb-ta;
        if(t<500){
            ta=microsegundos();
            for(k=0;k<1000;k++){
                ascendente(vector,i);
                ord_monticulo(vector,i);
            }
            tb=microsegundos();
            t1=tb-ta;
            ta=microsegundos();
            for(k=0;k<1000;k++){
                ascendente(vector,i);
            }
            tb=microsegundos();
            t2=tb-ta;
            t=(t1-t2)/k;
        }

        printf("%d      %f\n",i,t);
    }
}

void imprimirDescendente(int vector[]){
    int i,k;
    double t,ta,tb,t1,t2;
    printf("\nDESCENDENTE\n");
    printf("n         t\n");
    for(i=500;i<=32000;i=i*2) {
        descendente(vector, i);
        ta=microsegundos();
        ord_monticulo(vector,i);
        tb=microsegundos();
        t=tb-ta;
        if(t<500){
            ta=microsegundos();
            for(k=0;k<1000;k++){
                descendente(vector,i);
                ord_monticulo(vector,i);
            }
            tb=microsegundos();
            t1=tb-ta;
            ta=microsegundos();
            for(k=0;k<1000;k++){
                descendente(vector,i);
            }
            tb=microsegundos();
            t2=tb-ta;
            t=(t1-t2)/k;
        }
        printf("%d      %f\n",i,t);
    }
}

void imprimirAleatorio(int vector[]){
    int i,k;
    double t,ta,tb,t1,t2;
    printf("\nALEATORIO\n");
    printf("n         t\n");
    for(i=500;i<=32000;i=i*2) {
        aleatorio(vector, i);
        ta=microsegundos();
        ord_monticulo(vector,i);
        tb=microsegundos();
        t=tb-ta;
        if(t<500){
            ta=microsegundos();
            for(k=0;k<1000;k++){
                aleatorio(vector,i);
                ord_monticulo(vector,i);
            }
            tb=microsegundos();
            t1=tb-ta;

            ta=microsegundos();
            for(k=0;k<1000;k++){
                aleatorio(vector,i);
            }
            tb=microsegundos();
            t2=tb-ta;
            t=(t1-t2)/k;
        }
        printf("%d      %f\n",i,t);
    }
}

int main() {
    int i;
    int vector[32000];

    imprimirAscendente(vector);
    imprimirDescendente(vector);
    imprimirAleatorio(vector);

    for(i=0;i<TAM;i++){
    //    free(vectorDeMonticulo(i));
    }

    return 0;
}