#include "stdio.h"
#include "stdlib.h"
#include "time.h"
#define TRUE 1
#define FALSE 0

int A[2000],AOUNO[2000],B[3000],C[4000],D[5000],E[6000],F[7000];
FILE *doc;

void num_random(int vec[], int tam)
{

        srand(time(NULL));

        for (int i = 0; i < tam; ++i)
        {
                vec[i]=(rand()%10000)+1;
        }

}

void reducirder(int ini, int fin,int vec[]){

    int izq, der, pos, aux, band;
    izq=ini;
    der=fin;
    pos=fin;
    band=TRUE;

    while(band==TRUE){
        band=FALSE;
        while(vec[pos]>=vec[izq] && pos!= izq)
                izq=izq+1;
        if(pos!=izq){
                aux=vec[pos];
                vec[pos]=vec[izq];
                vec[izq]=aux;
                pos=izq;

            while(vec[pos]<= vec[der] && pos != der)
            der=der-1;
        if(pos != der){
            band=TRUE;
            aux=vec[pos];
            vec[pos]=vec[der];
            vec[der]=aux;
            pos=der;
            }
        }
    }
    if((pos-1) >ini)
        reducirder(ini,pos-1,vec);
    if(fin > (pos +1))
        reducirder(pos+1,fin,vec);
}

void reducirizq(int ini, int fin,int vec[]){

    int izq, der, pos, aux, band;
    izq=ini;
    der=fin;
    pos=ini;
    band=TRUE;

    while(band==TRUE){
        band=FALSE;
        while(vec[pos]<= vec[der] && pos != der)
            der=der-1;
        if(pos != der){
            aux=vec[pos];
            vec[pos]=vec[der];
            vec[der]=aux;
            pos=der;
            while(vec[pos]>=vec[izq] && pos!= izq)
                izq=izq+1;
            if(pos!=izq){
                band=TRUE;
                aux=vec[pos];
                vec[pos]=vec[izq];
                vec[izq]=aux;
                pos=izq;
            }
        }
    }
    if((pos-1) >ini)
        reducirizq(ini,pos-1,vec);
    if(fin > (pos +1))
        reducirizq(pos+1,fin,vec);
}

void quicksortizq(int vec[],int N){
    reducirizq(0,N-1,vec);
}

void quicksortder(int vec[],int N){
    reducirder(0,N-1,vec);
}

int main()
{

    doc = fopen("tiempos.txt","w");

    //Variables aux
    int tamano;
	clock_t inicio, fin;
    //procesando vector de 2000 izq
    tamano=sizeof(A)/sizeof(int);
    num_random(A,tamano);
    for(int i=0;i<tamano;i++) A[i]=AOUNO[i];

    inicio=clock();
    quicksortizq(AOUNO,tamano);
    fin=clock();
    printf("%f\n", (float)(fin-inicio)/(float)CLOCKS_PER_SEC);
    fprintf(doc,"A[1]=%f \n",(float)(fin-inicio)/(float)CLOCKS_PER_SEC);
    //
   	//procesando vector de 2000 der
    //Copiando vector
    for(int i=0;i<tamano;i++) A[i]=AOUNO[i];
    inicio=clock();
    quicksortder(AOUNO,tamano);
    fin=clock();
    printf("%f\n", (float)(fin-inicio)/(float)CLOCKS_PER_SEC);
    fprintf(doc,"A[N]=%f \n",(float)(fin-inicio)/(float)CLOCKS_PER_SEC);
    //

    fclose(doc);
    system("pause");
    return 0;

}