Skip to content
Snippets Groups Projects
Select Git revision
  • main default protected
1 result

ordenacao.c

Blame
  • ordenacao.c 6.24 KiB
    #include "ordenacao.h"
    #include <string.h>
    #include <stdio.h>
    #include <stdlib.h>
    
    
    void getNome(char nome[]){
    	//substitua por seu nome
    	strncpy(nome, "Vinicius Fontoura de Abreu", MAX_CHAR_NOME);
    	nome[MAX_CHAR_NOME-1] = '\0';//adicionada terminação manual para caso de overflow
    }
    
    unsigned int getGRR(){
    	return 20206873;
    }
    
    //a função a seguir deve retornar o seu número de GRR
    unsigned int getGRR();
    
    int buscaSequencialCompleta(int vetor[],int a, int b, int valor, int* numComparacoes) {
    	//printf("%d\n",b);
    	if (a>b)
    		return a-1;
    
    	*numComparacoes+=1;
    	if (valor==vetor[b]) {
    		return b;
    	}
    	return buscaSequencialCompleta(vetor,a,b-1,valor,numComparacoes);
    }
    
    int buscaSequencial(int vetor[], int tam, int valor, int* numComparacoes){
    	int a = 0;
    	//caso base
    	if (a > tam)
    		return -1;
    
    	return buscaSequencialCompleta(vetor,0,tam-1,valor,numComparacoes);
    }
    
    //usada para processar a busca binaria corretamente
    int buscaBinariaCompleta(int vetor[], int tam, int inicio, int valor, int* numComparacoes) {
    	int meio;
    	if (inicio > tam)
    		return -1;
    
    	meio = (tam+inicio)/2;
    
    	if (vetor[meio] == valor) {
    		*numComparacoes+=1;
    		return meio;
    	}
    
    	//busca a esquerda
    	if (vetor[meio] > valor) {
    		*numComparacoes+=1;
    		return buscaBinariaCompleta(vetor,meio-1,inicio,valor,numComparacoes);
    	}
    	//busca a direita
    	*numComparacoes+=1;
    	return buscaBinariaCompleta(vetor,tam,meio+1,valor,numComparacoes);
    }
    
    int buscaBinaria(int vetor[], int tam, int valor, int* numComparacoes){
    	int a,b,meio;
    	a = 0;
    	b = tam;
    	meio = tam/2;
    	if (a > b) {
    		return -1;
    	}
    
    	if (vetor[meio] == valor) {
    		*numComparacoes+=1;
    		return meio;
    	}
    
    	// busca a esquerda
    	if (vetor[meio] > valor) {
    		*numComparacoes+=1;
    		return buscaBinariaCompleta(vetor,meio-1,a,valor,numComparacoes);
    	}
    	//busca a direita
    	*numComparacoes+=1;
    	return buscaBinariaCompleta(vetor,b,meio+1,valor,numComparacoes);
    }
    
    
    void troca(int vetor[], int a, int b) {
    	int x;
    	x = vetor[a];
    	vetor[a] = vetor[b];
    	vetor[b] = x;
    }
    
    
    void insere(int vetor[], int a, int b,int* numComparacoes) {
    	int posicao,i;
    	//busca a posicao correta do ultimo elemento
    	posicao = buscaSequencial(vetor,b-1,vetor[b],numComparacoes);
    	i = b;
    	//enquanto o ultimo elemento for maior que o elemento na sua posicao correta
    	while (i > posicao+1) {
    		//faz a troca ate chegar na posicao correta
    		troca(vetor,i,i-1);
    		i--;
    	}
    }
    
    int insertionSortCompleto(int vetor[], int a, int b, int* numComparacoes) {
    	if (a >= b)
    		return b;
    	//vai ser chamado ate chegar no vetor de tamanho 1
    	insertionSortCompleto(vetor,a,b-1,numComparacoes);
    	//insere cada elemento na posicao correta
    	insere(vetor,a,b,numComparacoes);
    	return *numComparacoes;
    }
    
    
    int insertionSort(int vetor[], int tam){	
    	int numComparacoes;
    	numComparacoes = 0;
    	//caso base
    	if (0 >= tam)
    		return tam;
    	//faz a primeira chamada
    	insertionSortCompleto(vetor,0,tam,&numComparacoes);
    
    	return numComparacoes;
    }
    
    //wrapper para fazer a contagem do numero de comparacoes
    int selectionSortCompleto(int vetor[], int a, int b, int* numComparacoes) {
    	int inicio, menor;
    	if (a >= b)
    		return a;
    	inicio = a;
    	//o menor elemento dentro do vetor(sera procurado ainda)
    	menor = a;
    
    	//do inicio ate o fim do vetor, checamos qual eh o menor valor
    	for (int i=a;i<b;i++) {
    		//se o valor em i for < que o valor em inicio
    		if (vetor[i]<vetor[inicio]) {
    			*numComparacoes+=1;
    			//marca o elemento em i como o menor
    			menor = i;
    			//ajusta o inicio para i
    			inicio = i;
    		}
    	}
    	//faz a troca do primeiro com o
    	troca(vetor,a,menor);
    	//retorna a funcao para o proximo item do vetor
    	return selectionSortCompleto(vetor, a+1, b, numComparacoes);
    
    }
    
    
    int selectionSort(int vetor[], int tam){
    	int a, numComparacoes;
    	numComparacoes = 0;
    	a = 0;
    	//caso base
    	if (a >= tam)
    		return a;
    	//primeira chamada
    	selectionSortCompleto(vetor, a, tam, &numComparacoes);
    	return numComparacoes;
    }
    
    //copia para o vetor V com inicio em a e final em b a partir do vetor aux
    void copiar(int v[], int a, int b, int aux[]) {
    	int i = 0;
    	while (i <= b-a) {
    		v[a+i] = aux[i];
    		i++;
    	}
    	return;
    }
    
    void merge(int v[], int a, int m, int b, int* numComparacoes) {
    	int k,i,j,p;
    	int u[b];
    	//caso base
    	if (a >= b)
    		return;
    	//iterador do vetor auxiliar
    	k=0;
    	//iterador do vetor a esquerda
    	i=a;
    	//iterador do vetor a direita
    	j=m+1;
    	//enquanto o vetor auxiliar nao estiver preenchido por completo
    	while (k <= b-a) {
    		//se o vetor a direita tiver acabado OU
    		//o vetor a esquerda acabo E
    		//o elemento do primeiro for <= ao elemento do segundo
    		if (j > b || (i <= m && v[i] <= v[j])) {
    			*numComparacoes+=1;
    			//marca o elemento em i
    			p = i;
    			i++;
    		}
    		else {
    			//marca o elemento em j
    			p = j;
    			j++;
    		}
    		//copia o valor em p para o vetor aux
    		u[k] = v[p];
    		k++;
    	}
    	//copia o vetor aux para o vetor original
    	copiar(v,a,b,u);
    	return;
    }
    
    //wraper para o MergeSort
    int mergeSortCompleto(int vetor[], int a, int b, int* numComparacoes) {
    	int m;
    	//caso base
    	if (a >= b)
    		return b;
    	// valor de M
    	m = (a+b)/2;
    	//faz a primeira chamada e ordena recursivamente cada metade gerada
    	mergeSortCompleto(vetor,a,m,numComparacoes);
    	mergeSortCompleto(vetor,m+1,b,numComparacoes);
    	//junta cada metade gerada apos todas as chamadas recursivas
    	merge(vetor,a,m,b,numComparacoes);
    	return *numComparacoes;
    }
    
    int mergeSort(int vetor[], int tam){
    	int numComparacoes = 0;
    	//faz a primeira chamada
    	mergeSortCompleto(vetor,0,tam,&numComparacoes);
    	return numComparacoes;
    }
    
    //coloca o pivo na posicao correta
    int particionar(int v[], int a, int b,int* numComparacoes) {
    	int x,m;
    	//pivo da particao
    	x = v[b];
    	m = a;
    	//percorre o vetor e faz a troca se o elemento em i é <= ao pivo
    	for (int i=a;i<b;i++) {
    		if (v[i] <= x) {
    			*numComparacoes+=1;
    			troca(v,m,i);
    			m++;
    		}
    	}
    	//troca o ultimo elemento com o primeiro
    	troca(v,m,b);
    	return m;
    }
    
    int quickSortCompleto(int vetor[],int a, int b, int* numComparacoes) {
    	int m;
    	//caso base
    	if (a >= b) 
    		return a;
    	//faz a primeira particao ordena recursivamente cada metade gerada
    	m = particionar(vetor,a,b,numComparacoes);
    	quickSortCompleto(vetor,a,m-1,numComparacoes);
    	quickSortCompleto(vetor,m+1,b,numComparacoes);
    	return *numComparacoes;
    }
    
    int quickSort(int vetor[], int tam){
    	int a;
    	int numComparacoes = 0;
    	if (0 >= tam)
    		return -1;
    	a = 0;
    
    	quickSortCompleto(vetor,a,tam,&numComparacoes);
    	return numComparacoes;
    }