p2 (╯°□°）╯︵ ┻━┻

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

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 - izq + 1)) + 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[j];V[j]=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;
    printf("Ordenacion rapida con inicializacion aleatoria\n");
    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]);
    }

    printf("\nOrdenacion rapida con inicializacion descendiente\n");
    descendente(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);

    }

    printf("\n");
    test2();
    printf("\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();
        ord_rapida(a,n);
        tb=microsegundos();

        t=tb-ta;
        if(t<500){
            ta=microsegundos();
            for(k=0;k<100;k++){
                descendente(a,n);
                ord_rapida(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);

    }


    return 0;
}