Select Git revision
ordenacao.c
-
Vinícius Fontoura authoredVinícius Fontoura authored
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;
}