p1

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <sys/time.h>
#include <math.h>
#define UMBRAL 1

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


void ordenacionPorInsercion (int v[],int n) {
    int i;
    int j;
    int x;

    for (i = 1; i <= n - 1; i++) {
        x = v[i];
        j = i - 1;
        while (j > -1 && v[j] > x) {
            v[j + 1] = v[j];
            j = j - 1;
        }
        v[j + 1] = x;
    }
}
void inicializar_semilla() {
    srand(time(NULL));
}
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 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 ordenarAux (int V[], int izq, int der) {
    int i;
    int j;
    int x;
    int Aux;
    int pivote;
    if (izq + UMBRAL <= der) {
        x = (rand() % (der + 1 - izq)) + izq;
        pivote=V[x];
        Aux=V[izq]; V[izq]=V[x]; V[x]=Aux;
        i=izq +1;
        j= der;
        while(i<=j){
            while(i<= der && V[i] < pivote){
                i=i+1;
            }
            while(V[j]>pivote){
                j=j-1;
            }

            if(i<j){
                Aux=V[i];V[i]=V[j];V[j]=Aux;
                i=i+1;
                j=j-1;
            }
        }
        Aux=V[izq];V[izq]=V[der];V[der]=Aux;
        ordenarAux(V,izq,j-1);
        ordenarAux(V,j+1,der);
    }
}
void ord_rapida(int v [], int n) {
    ordenarAux(v, 0, n-1);
    if (UMBRAL > 1)
        ordenacionPorInsercion(v, n);
}


void test(){
    inicializar_semilla();
    int tamano=20;
    int a[tamano];
    int i;

    printf("Ordenacion por insercion con inicializacion aleatoria\n");
    aleatorio(a,tamano);
    for(i=0;i<tamano;i++){
        printf("%d ",a[i]);
    }
    printf("\n");
    ordenacionPorInsercion(a,tamano);
    for(i=0;i<tamano;i++){
        printf("%d ",a[i]);
    }
    printf("\nOrdenacion por insercion con inicializacion descendiente\n");
    descendente(a,tamano);
    for(i=0;i<tamano;i++){
        printf("%d ",a[i]);
    }
    printf("\n");
    ordenacionPorInsercion(a,tamano);
    for(i=0;i<tamano;i++){
        printf("%d ",a[i]);
    }
}

void test2(){
    inicializar_semilla();
    int tamano=20;
    int a[tamano];
    int i;
    aleatorio(a,tamano);
    for(i=0;i<tamano;i++){
        printf("%d ",a[i]);
    }
    printf("\n");
    ord_rapida(a,tamano);
    for(i=0;i<tamano;i++){
        printf("%d ",a[i]);
    }
}




int main() {
    test();
    printf("\n");

    int k;
    double ta,tb, t1, t2, t, x, y, z;
    int n;


    printf("           n           t(n)      t(n)/n^1.8      t(n)/n^2     t(n)/n^2.2\n");
    for(n=500;n<=32000;n=n*2){
        int a[n];
        descendente(a,n);
        ta=microsegundos();
        ordenacionPorInsercion(a,n);
        tb=microsegundos();

        t=tb-ta;
        if(t<500){
            ta=microsegundos();
            for(k=0;k<100;k++){
                descendente(a,n);
                ordenacionPorInsercion(a,n);
            }
            tb=microsegundos();
            t1=tb-ta;

            ta=microsegundos();
            for(k=0;k<100;k++){
                descendente(a,n);
            }
            tb=microsegundos();
            t2=tb-ta;
            t=(t1-t2)/k;
        }

        x = t / pow(n,1.8);
        y = t / pow(n,2);
        z = t / pow(n, 2.2);
        printf("%12d%15.3f%15.6f%15.6f%15.6f\n", n, t, x, y, z);

    }
    /*

    int k;
    double t1, t2, t, x, y, z;
    int cont;
    int n;

    inicializar_semilla();
    int tamano = 500;
    int a[tamano];
    aleatorio(a,tamano);
    int izq;
    int der;
    izq = a[1];
    der = a[500];

    t1 = microsegundos();
    ordenarAux(a, izq, der);
    t2 = microsegundos();

    t = t2 - t1;

    if (t < 500) {
        t1 = microsegundos();
        for (k = 0; k <= 100; k++) {
            ordenarAux(a, izq, der);
        }
        t2 = microsegundos();
        t = (t2 - t1) / k;
    }

    for (cont = 1; cont <= 3; cont++) {
        for (n = 500; n <= 32000; n = n * 2) {
            inicializar_semilla();
            int b[n];
            aleatorio(b,n);
            t1 = microsegundos();
            ordenarAux(b, izq, der);
            t2 = microsegundos();
            t = t2 - t1;
            x = t / pow(n,1.8);
            y = t / pow(n,2);
            z = t / pow(n, 2.2);
            printf("%12d%15.3f%15.6f%15.6f%15.6f\n", n, t, x, y, z);
        }
        printf("\n");
    }
*/

    printf("\nTEST2\n");
    test2();
    return 0;
}