#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

//estruturas
typedef struct _contato{
char n[4];

}TpContato;

TpContato *inicializa_contato(){
	return NULL;
}

int menu(){
	int opcao;
	printf ("*********************************\n");
	printf ("*	ESCOLHA A OPÇAO		*\n");
	printf ("*********************************\n");
	printf ("*	1)CRIAR VETOR		*\n");
	printf ("*	2)INSERTION S.		*\n");
	printf ("*	3)SELECTION S.		*\n");
	printf ("*	4)QUICK S.		*\n");
	printf ("*	5)MERGE S.		*\n");
	printf ("*	6)SAIR			*\n");
	printf ("*********************************\n");
	scanf("%d",&opcao);
	return opcao;
}

//-------------------------------

//-------------------------------
//Funçoẽs relacionadas a vetores

TpContato *cria_vetor(TpContato *a,int n){
	int i = 0, tabela, x,indice;
	TpContato *novo;
	char num[10]; //0123456789
	char numero[4];
	while(i<n){
		novo = (TpContato *) malloc(sizeof(TpContato));
		tabela = 48;
		for(x = 0; x < 10; x++){//char "num" recebendo os inteiros de 0 a 9
			num[x] = tabela;
			tabela++;
		}
		for(x = 0; x < 3; x++){ //escolhe um dos inteiros para formar o numero aleatorio
			indice = rand()%10;
			numero[x] = num[indice];
		}
		strcpy(novo->n,numero);
		a[i] = *novo;
		i++;
	}
	return a;
}
TpContato *copia_vetor(TpContato *a, int tam){
	int i;
	TpContato *novo;
	novo = (TpContato *) malloc(sizeof(TpContato)*tam);
	for(i = 0; i < tam; i++){
		strcpy(novo[i].n,a[i].n);
	
	}
	return novo;
}
	
void imprime_vetor(TpContato *a,int tam){
	int i = 0;
	printf("--------------\n");
	while(i<tam){
		printf("Valor: %s\n",a[i].n);
		printf("--------------\n");
		i++;
	}
}

TpContato *selectionSort_vetor(TpContato *v, int n){
	int i,j,menor;
	clock_t inicio,fim;
	double resultado;
	char copia[40];
	TpContato *aux;
	inicio = clock();
	aux = copia_vetor(v,n);
	for(i = 0; i<n ; i++){
		menor = i;
		for(j = i+1 ; j<n ; j++){
			if(strcmp(aux[j].n,aux[menor].n)<=-1){
				menor = j;
			}
		}
		if( i != menor){
			strcpy(copia,aux[menor].n);
			strcpy(aux[menor].n,aux[i].n);
			strcpy(aux[i].n,copia);
			
		}
	}
	fim = clock();
	resultado = (double)(fim - inicio)/CLOCKS_PER_SEC;
	printf("selectionSort_vetor\n");
	imprime_vetor(aux,n);
	printf("Tempo: %f (segundos)\n\n",resultado);
	return v;
}

TpContato *insertionSort_vetor(TpContato *v, int n){
	int j,i;
	clock_t inicio,fim;
	double resultado;		
	char number[30];
	TpContato *aux;
	inicio = clock();
	aux = copia_vetor(v,n);	

	for(j=1;j<n;j++){
		strcpy(number,aux[j].n);
		i = j-1;
		while(i>=0 && (strcmp(number,aux[i].n))<=-1){
			strcpy(aux[i+1].n,aux[i].n);
			i--;
		}
		strcpy(aux[i+1].n,number);
	}
	fim = clock();
	resultado = (double)(fim - inicio)/CLOCKS_PER_SEC;
	printf("insertionSort_vetor\n");
	imprime_vetor(aux,n);
	printf("Tempo: %f (segundos)\n\n",resultado);	
	return v;
}

 
void trocaValores(TpContato *a,TpContato *b){
	TpContato *aux;
	aux = (TpContato *) malloc(sizeof(TpContato));
	strcpy(aux->n,a->n);
	strcpy(a->n,b->n);
	strcpy(b->n,aux->n);
	free(aux);
}

int divide(TpContato vec[], int p, int q){
		int i, j;
    i = p;
    for (j = p ; j < q; ++j){
       if((strcmp(vec[j].n,vec[p].n))<=-1){
            ++i;
            trocaValores(&vec[i], &vec[j]);
        }
    }
    trocaValores(&vec[p], &vec[i]);
    return i;
}
 
void quickSort(TpContato vec[], int p, int q){
	int r;
    if (q > p){
        r = divide(vec, p, q);
        quickSort(vec, p, r - 1);
        quickSort(vec, r + 1, q);
    }
}

void funcao_quick_vetor(TpContato *a, int p, int q){
	int tam = q;
    clock_t inicio,fim;
    double resultado;
	TpContato *aux;
	inicio = clock();
	aux = inicializa_contato();
	aux = copia_vetor(a,tam);
    //imprime_vetor(aux, tam);
    quickSort(aux,p,q);
	fim = clock();
	resultado = (double)(fim - inicio)/CLOCKS_PER_SEC;
	printf("quickSort_vetor\n");
	imprime_vetor(aux,tam);
	printf("Tempo: %f (segundos)\n\n",resultado);
}

void Merge_Sort(TpContato *A, int p,int q,int r){
	TpContato *L = NULL, *R = NULL;
	int n1 = q - p + 1,n2 = r - q;
	int i, j, k;

	L = malloc(sizeof(TpContato)*(n1+1));
	R = malloc(sizeof(TpContato)*(n2+1));

	for(i = 0; i < n1; i++) L[i] = A[p+i];
	for(j = 0; j < n2; j++) R[j] = A[q+j+1];

	
	for( i = j = 0, k = p; k <= r; k++){
		if (strcmp(L[i].n, R[j].n) <= 0){
			A[k] = L[i++];
		}else{
			A[k] = R[j++];
		}
	}
}

void Merge(TpContato* A,int p,int r){
	int q;
	if(p < r){
		q = (p + r) / 2;
		Merge(A,p,q);
		Merge(A,q+1,r);
		Merge_Sort(A,p,q,r);
	}
}

void funcao_merge_vetor(TpContato *A, int p, int r){
    clock_t inicio,fim;
    double resultado;
    TpContato *aux;
    int tam = r;
	inicio = clock();
	aux = copia_vetor(A,tam+1);
	Merge(aux,p,r);
	fim = clock();
	resultado = (double)(fim - inicio)/CLOCKS_PER_SEC;
	printf("Merge \n");
	imprime_vetor(aux,tam+1);
	printf("Tempo: %f (segundos)\n\n",resultado);
}



int main(){ 
	int opcao = 0;
	int tam = 0;
	TpContato *vetor;
	vetor = inicializa_contato();
	//system("clear");
	
	while(opcao!=6){
	opcao = menu();
	switch (opcao){
		case 1:
		system("clear");			
		printf ("*	DIGITE O TAMANHO	*\n");
		scanf("%d",&tam);
		vetor = (TpContato *) malloc(sizeof(TpContato)*tam);
		cria_vetor(vetor,tam);
		imprime_vetor(vetor,tam);
		continue;
		case 2:
				insertionSort_vetor(vetor,tam);
		continue;
		case 3:
		
				selectionSort_vetor(vetor,tam);
			
		continue;
		case 4:
		        
				funcao_quick_vetor(vetor,0,tam);
		continue;
		
		case 5:
		if(vetor!=NULL){
			funcao_merge_vetor(vetor,0,tam-1);
		}else{
			printf ("* NENHUM VETOR FOI CRIADO	*\n\n");
		}
		continue;		
		case 6:
		return 0;
		default:
		printf ("*	OPCAO INVALIDA!		*\n");
	}
}
return 0;
}