p4.c

#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;
    int HijoIzq;
    int HijoDer;
    do {
        HijoIzq=2*i+1;
        HijoDer=2*i+2;
        j=i;
        if (HijoDer <= m->ultimo && m->vector[HijoDer] > m->vector[i]) {
            i = HijoDer;
        }
        if (HijoIzq <= m->ultimo && m->vector[HijoIzq] > m->vector[i]) {
            i = HijoIzq;
        }
        aux = m->vector[j];
        m->vector[j] = m->vector[i];
        m->vector[i] = aux;
    }while(j!=i);

}

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 = n - 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 n, monticulo *m){
    int i;
    int j;
    m->ultimo=n;

    for(j=0;j<n;j++){
        m->vector[j]=a[j];
    }
    for (i = n/2; i >= 0; i--) {
        Hundir(m, i);
    }
}

int eliminar_mayor(monticulo *m){
    int x;

    if(m==NULL){
        printf("Error monticulo vacio\n");
        exit(0);
    }
    x=m->vector[0];
    m->vector[0]=m->vector[m->ultimo];
    m->ultimo--;
    if(m->ultimo>0) {
        Hundir(m, 0);
    }
    return x;
}

void ord_monticulo(int V[], int n){
    int i;
    monticulo *M = malloc(sizeof(monticulo));
    crear_monticulo(V,n,M);

    for(i=M->ultimo-1;i>=0;i--){
        V[i]= eliminar_mayor(M);
    }

    free(M);
}

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

    printf("ASCENDENTE\n");
    printf("\tn\t\tt     \t(n)/n^0.9       \tt(n)/(n*log(n))    \tt(n)/n^1.4\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;
        }

        x = t / pow(i, 0.9);
        y = t / (i*log(i));
        z = t / pow(i, 1.4);
        printf("%12d%15.3f%15.6f%15.6f%15.6f\n", i, t, x, y, z);
    }
}

void imprimirDescendente(int vector[]){
    int i,k;
    double t,ta,tb,t1,t2,x, y, z;
    printf("\nDESCENDENTE\n");
    printf("\tn\t\tt     \t(n)/n^0.9       \tt(n)/(n*log(n))    \tt(n)/n^1.4\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;
        }

        x = t / pow(i,0.9);
        y = t / (i*log(i));
        z = t / pow(i, 1.4);
        printf("%12d%15.3f%15.6f%15.6f%15.6f\n", i, t, x, y, z);
    }
}

void imprimirAleatorio(int vector[]){
    int i,k;
    double t,ta,tb,t1,t2,x, y, z;
    printf("\nALEATORIO\n");
    printf("\tn\t\tt     \t(n)/n^0.9       \tt(n)/(n*log(n))    \tt(n)/n^1.4\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;
        }

        x = t / pow(i,0.9);
        y = t / (i*log(i));
        z = t / pow(i, 1.4);
        printf("%12d%15.3f%15.6f%15.6f%15.6f\n", i, t, x, y, z);
    }
}

void imprimirAscendenteCrear(int vector[]){
    int i,k;
    double t,ta,tb,t1,t2,x, y, z;
    monticulo *M = malloc(sizeof(monticulo));
    printf("\nCREAR MONTICULO ASCENDENTE\n");
    printf("\tn\t\tt     \t(n)/n^0.9       \tt(n)/n  \tt(n)/n^1.4\n");
    for(i=500;i<=32000;i=i*2) {
        ascendente(vector, i);
        ta=microsegundos();
        crear_monticulo(vector,i,M);
        tb=microsegundos();
        t=tb-ta;
        if(t<500){
            ta=microsegundos();
            for(k=0;k<1000;k++){
                ascendente(vector,i);
                crear_monticulo(vector,i,M);
            }
            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;
        }

        x = t / pow(i,0.9);
        y = t / (i);
        z = t / pow(i, 1.4);
        printf("%12d%15.3f%15.6f%15.6f%15.6f\n", i, t, x, y, z);
    }
    free(M);
}


void test(){
    int i;
    int a[10] = {5,3,4,8,0,2,1,6,7,9};
    int ultimo=10;
    monticulo *M = malloc(sizeof(monticulo));

    crear_monticulo(a,ultimo,M);
    printf("Vector inicial\n");
    for(i=0;i<M->ultimo;i++){
        printf("%d",a[i]);
    }
    printf("\nCrear monticulo\n");
    for(i=0;i<M->ultimo;i++){
        printf("%d",M->vector[i]);
    }
    printf("\nOrdenacion por monticulos\n");
    ord_monticulo(a,ultimo);

    for(i=0;i<M->ultimo;i++){
        printf("%d",a[i]);
    }
    free(M);
    printf("\n");
}

int main() {
    int vector[32000];

    printf("TEST\n");
    test();
    printf("\n");

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

    return 0;
}