/*

	Exerício Análise de Algorítmos
	Professor: Rodrigo Senra
	
Cesar Henrique Kállas	opensrc@gmx.net
RA: 02099224

Data entrega: 08/10/2003

Função:

1) Implementar os seguintes algoritmos de ordenação: Bubble, Selection, Insertion, QuickSort, Merge e Heap.
2) Analisar o caso médio de algum deles (exceto bubble que é trivial).
3) Implementar casos de teste para os algoritmos com vetores com: 256, 512, 1024, 2048, 4196.
4) Plotar os gráficos do tempo que cada algoritmo levou para executar versus tamanho do vetor. 
> Tecer comentários sobre: dificuldades no entendimento/implementação (não conta ponto negativo é só para eu saber),
impressões sobre eficiência dos algoritmos, outros comentários quaisquer. 

*/

#include <iostream.h>
#include <time.h>
#include <stdlib.h>

#define pausa system("sleep 5s");

struct vetor {
	int numero;
};

void preencher_vetor(struct vetor *vet, int tamanho)
{

	for(int i=0; i<tamanho/2; i++)
	{
		vet[i].numero = rand() % tamanho;
		vet[tamanho-i] = rand() % tamanho;
	}
	
}

void imprima_vetor(struct vetor *vet, int tamanho,double tempo, int metodo)
{
	int colunas=0;
	for(int i=0; i<tamanho; i++)
	{
		if(colunas == 10)
		{
			cout << "\n";
			colunas=0;
		}
		
		cout << vet[i].numero << "\t";
		colunas++;
	}
	cout << "\n\n Status:\n";
	cout << "\tMetodo usado: ";
	switch(metodo)
	{
		case 0: cout << "Gerar o vetor";	break;
		case 1: cout << "Bolha";		break;
		case 2: cout << "Selection Sort";	break;
		case 3: cout << "Insertion Sort";	break;
		case 4: cout << "Quick Sort";	break;
		case 5: cout << "Merge Sort";	break;
		case 6: cout << "Heap Sort";	break;
		default: break;
	}
			
	cout << "\n\tNumero de elementos do vetor = " << tamanho;
	cout << "\n\tTempo gasto = " << tempo << " segundo(s)";
	
}

	
void bolha(struct vetor *vet, int tamanho)
{
	struct vetor *aux;	
	aux = new struct vetor;
	
	int i,j;
	int teste=1;
	
	for(i=0; i<tamanho-1 && teste==1; i++){
		teste=0;
		for(j=0; j<tamanho-i-1; j++)
		{
			if(vet[j].numero > vet[j+1].numero)
			{
				teste=1;
				*aux = vet[j];
				vet[j] = vet[j+1];
				vet[j+1] = *aux;
			}
		}
	}
}


void quicksort(struct vetor *vet,struct vetor *aux,int ini,int fim){
	
	int flag=1,i,j;
			
	if(ini<fim){
		i=ini;
		j=fim;
		while(i<j){
			if(vet[i].numero > vet[j].numero)
			{
				*aux = vet[i];
				vet[i] = vet[j];
				vet[j] = *aux;
				flag=flag*(-1);
			}
			if(flag==1) j--;
				else
				i++;
		}
		quicksort(vet,aux,ini,j-1);
		quicksort(vet,aux,j+1,fim);
	}
}

void selection(struct vetor *vet,struct vetor *aux, int tamanho)
{
    int menor;
    
	for (int i = 0; i < tamanho; i++)
	{
		menor = i;
		for (int j = i; j < tamanho; j++)
		{
			if (vet[j].numero < vet[menor].numero)
				menor = j;
			*aux = vet[i];
			vet[i] = vet[menor];
			vet[menor] = *aux;
		}
	}
}

void insertion(struct vetor *vet,struct vetor *aux, int tamanho)
{
	int i,k;
	
	for( k=1; k<tamanho; k++)
	{
		*aux = vet[k];
		for ( i=k-1; i>=0 && aux->numero < vet[i].numero; i--)
			vet[i+1] = vet[i];
		vet[i+1] = *aux;
	}
}

void add_heap(struct vetor *vet, struct vetor *aux, int l, int r)
{ 
	int i,j;
	i=l;
	j = 2*i+1;
	*aux = vet[i];
	
	while (j<= r)
	{
		if(j<=r-1)
			if(vet[j].numero < vet[j+1].numero)
			j++;
			
		if(aux->numero < vet[j].numero)
		{
			vet[i] = vet[j];
			i=j;
			j=2*i+1;
		}
		else
			j = r+1;
	}
	vet[i] = *aux;
}


void heap(struct vetor *vet, struct vetor *aux, int tamanho)
{  
	int r,l;
	r =tamanho-1;
	
	for (l = tamanho/2-1; l>=0; l--)
		add_heap(vet,aux,l,r);
	l=0;
	
	for (r=tamanho-2; r >= 0; r--)
	{
		*aux = vet[0];
		vet[0] = vet[r+1];
		vet[r+1] = *aux;
		add_heap(vet,aux,l,r);
	}
}

void merge(struct vetor *vet,int left, int right)
{
	int mid=(left+right)/2, size = (right-left+1);
	struct vetor *aux;
	
	aux = new struct vetor[size];
	
	int count=0;
	for(int x=left;x<=mid;x++,count++)
	{
		aux[count]=vet[x];
	}
	for(int x=right;x>=mid+1;x--,count++)
	{
		aux[count]=vet[x];
	}
	for(int x=0,y=size-1,put=left;x<=y;put++)
	{
		if(aux[x].numero <= aux[y].numero)
		{
			vet[put]=aux[x];
			x++;
		}
		else
		{
			vet[put]=aux[y];
			y--;
		}
	}

}

void mergesort (struct vetor *vet, int ini, int fim)
{
	int medio;
	if (ini < fim)
	{
		medio = (ini + fim)/2;
		mergesort (vet,ini,medio);
		mergesort (vet,medio+1,fim);
		merge (vet,ini,fim);
	}
}

	
int tamanho_vetor()
{
	int tamanho=9;
	
	while(tamanho>8)
	{
		cout << "\nOrdenar vetor com qtos numeros ?\n\n";
		cout << "\t0. 256 numeros\n";
		cout << "\t1. 512 numeros\n";
		cout << "\t2. 1024 numeros\n";
		cout << "\t3. 2048 numeros\n";
		cout << "\t4. 4196 numeros\n";
		cout << "\t5. 32000 numeros\n";
		cout << "\t6. 100 mil numeros\n";
		cout << "\t7. 1 milhão de numeros\n";
		cout << "\t8. 10 milhões de numeros [warning]\n";
		cout << "Opcao: ";
		cin >> tamanho;
	
		switch(tamanho)
		{
			case 0: return 256; break;
			case 1: return 512; break;
			case 2: return 1024; break;
			case 3: return 2048; break;
			case 4: return 4196; break;
			case 5: return 32000; break;
			case 6: return 100000; break;
			case 7: return 1000000; break;
			case 8: return 10000000; break;
			default: cout << "opcao invalida\n";
		}
	}
}
		
int main()
{
	struct vetor *vet,*aux,*copia;
	int opcao=9;
	time_t start,end;
	double tempo_bolha,tempo_heap,tempo_selection,tempo_insertion,tempo_quick,tempo_merge;
	
	while (opcao!=0)
	{
		cout << "\n\nOrdenacao, escolha o metodo: \n\n";
		cout << "\t1. Bolha\n";
		cout << "\t2. SelectionSort\n";
		cout << "\t3. InsertionSort\n";
		cout << "\t4. QuicksSrt\n";
		cout << "\t5. MergeSort\n";
		cout << "\t6. HeapSort\n";
		cout << "\t7. Estatistica de todos metodos juntos\n";
		cout << "\t0. para sair\n";
		cout << "Opcao: ";
		cin >> opcao;
			
		if(opcao > 0 && opcao < 8)
		{
			aux = new struct vetor;
				
			int tamanho = tamanho_vetor();
			vet = new struct vetor[tamanho];
			
			time(&start);
			preencher_vetor(vet,tamanho);
			time(&end);
			
			double tempo_gerar = difftime(end,start);
			imprima_vetor(vet,tamanho,tempo_gerar,0);
			cout << "\n\tO vetor acima esta desordenado\n";
			pausa;
						
			switch(opcao)
			{
				case 1: {
						time(&start);
						bolha(vet,tamanho);
						time(&end);
						break;
				}
				
				case 2: {
						time(&start);
						selection(vet,aux,tamanho);
						time(&end);
						break;
				}
				
				case 3: {
						time(&start);
						insertion(vet,aux,tamanho);
						time(&end);
						break;
				}
				
				case 4: {
						time(&start);
						quicksort(vet,aux,0,tamanho-1);
						time(&end);
						break;
				}
				
				case 5: {
						time(&start);
						mergesort(vet,0,tamanho-1);
						time(&end);
						break;
				}
				
				case 6: {
						time(&start);
						heap(vet,aux,tamanho);
						time(&end);
						break;
				}
				
				case 7: {	
						cout << "\nAguarde, processando....\n" << flush;	
						copia = vet;
												
						time(&start);
						bolha(vet,tamanho);
						time(&end);
						tempo_bolha = difftime(end,start);
						cout << "\nBolha [ok]\n" << flush ;
						
						vet = copia;
						time(&start);
						selection(vet,aux,tamanho);
						time(&end);
						tempo_selection = difftime(end,start);
						cout << "SelectionSort [ok]\n" << flush;
					
						vet = copia;
						time(&start);
						insertion(vet,aux,tamanho);
						time(&end);
						tempo_insertion = difftime(end,start);
						cout << "InsertionSort [ok]\n" << flush ;
					
						vet = copia;
						time(&start);
						quicksort(vet,aux,0,tamanho-1);
						time(&end);
						tempo_quick = difftime(end,start);
						cout << "QuickSort [ok]\n" << flush;
					
						vet = copia;
						time(&start);
						mergesort(vet,0,tamanho-1);
						time(&end);
						tempo_merge = difftime(end,start);
						cout << "MergeSort [ok]\n" << flush;
						
						vet = copia;
						time(&start);
						heap(vet,aux,tamanho);
						time(&end);
						tempo_heap = difftime(end,start);
						cout << "HeapSorte [ok]\n" << flush;
				}
			}
			if(opcao!=7)
			{
				imprima_vetor(vet,tamanho,difftime(end,start),opcao);
				cout << "\n\tO vetor acima esta ORDENADO\n";
				cout << "\tTempo para gerar vetor: " << tempo_gerar << " segundo(s)\n";
				
			}
				else
			{
				cout << "\n\n\tEstatistica de todos metodos\n";
				cout << "Numero de elementos no vetor: " << tamanho;
				cout << "\nDuracao para ordenacao (segundos)";
				cout << "\n\t- Bolha: " << tempo_bolha;
				cout << "\n\t- SelectionSort: " << tempo_selection;
				cout << "\n\t- InsertionSort: " << tempo_insertion;
				cout << "\n\t- QuickSort: " << tempo_quick;
				cout << "\n\t- MergeSort: " << tempo_merge;
				cout << "\n\t- HeapSort: " << tempo_heap;
				pausa;
				pausa;
			}		
				
		}
		else
			if(opcao==0)
			{
				return 0;
				break;
			}
			else
				cout << "\n\tEscolha uma opcao valida";
	}
}