Banco De Dados

3º Etapa

Nesta etapa o desafio consiste em usar vários algoritmos de ordenação e medir o desempenho de cada um deles com tabelas de dados. Essas tabelas terão 500, 5000, 50000 de tamanho, cada uma com três instâncias diferentes.

O desafio pede para usarmos novos valores para que as funções que geram números aleatórios possam variar de tabela para tabela. Para isso optamos pelos seguintes parâmetros:

Valores usados para gerar os números de cada instancia

Dentro do arquivo “atps.h” podemos encontrar a função “insere()” que será responsável por usar esses valores e preencher o total de nove instâncias senda três para cada tamanho de tabela.

1º Passo

Ao executar o programa pela primeira vez nos deparamos com a opção de rodar a versão 1.0, que tem todo o conteúdo da primeira etapa desse desafio ou a versão 2.0, essa sim nosso objetivo principal nesse momento.

Primeira tela do sistema

Ao escolher a opção 2 do sistema, todas as instâncias foram automaticamente geradas e as tabelas estão disponíveis para testes. Sendo assim é só escolher o algoritmo a ser usado. No exemplo abaixo vamos usar o quickSort como exemplo:

Menu para os algoritmos de ordenação

Com o tipo de algoritmo selecionado, vamos escolher o tipo de dados para o teste. De acordo com o desafio, podemos testar o algoritmo com uma tabela com dados aleatórios, ascendentes ou descendentes. Vamos escolher Dados Aleatórios, nesse momento o programa irá enviar para o algoritmo todas as três instancias de cada tabela e nos dar os resultados, como na próxima imagem.

Após realizar teste com todos os algoritmos o grupo chegou a conclusão de que, mesmo com dados já ordenados de forma ascendente, descendente ou aleatórias os resultados foram bem próximos. Levando em conta que todos os algoritmos são de ordenação, provavelmente em um problema real a tabela a ser ordenada será aleatória. Sendo assim os algoritmos com melhor desempenho foram quickSort e mergeSort. Ambos apresentaram resultados rápidos e com menor índice de comparações e trocas.

4º Etapa

Código fonte:

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

int quantidadeNos = 0;

typedef struct _no{

int chave;

int cont;

struct _no *esq, *dir, *pai;

}no;

no* auxPai = NULL;

void vaziaArvore(no *raiz){

if (raiz == NULL){

printf(" A arvore esta vazia\n\n");

}

else {

printf(" A arvore nao esta vazia\n\n");

}

}

void insere (int x, no **p){

if (*p==NULL){

*p=(no *)malloc(sizeof(no));

(*p)->chave=x;

(*p)->dir=NULL;

(*p)->esq=NULL;

(*p)->pai = auxPai;

(*p)->cont=0;

(*p)->cont++;

}

else{

if (x<(*p)->chave){

if((*p)->esq == NULL)

auxPai = *p;

insere(x, &(*p)->esq);

}

if(x>(*p)->chave){

if((*p)->dir == NULL)

auxPai = *p;

insere(x, &(*p)->dir);

}

if(x == (*p)->chave){

(*p)->cont++;

return;

}

}

}

int contaNos(no *p){

if(p != NULL){

quantidadeNos ++;

contaNos(p -> dir);

contaNos(p -> esq);

}

return quantidadeNos;

}

no* busca(no *arvore, int x){

if (arvore == NULL)

return NULL;

if (x == arvore->chave)

return arvore;

if (x < arvore->chave)

return busca(arvore->esq, x);

else

return busca(arvore->dir, x);

}

void consultarValor(no* raiz){

int num;

no* aux;

printf("Digite o numero procurado: ");

scanf("%d", &num);

aux = busca(raiz, num);

if (aux == NULL)

printf("Nao encontrado!\n");

else{

printf("Encontrado!\n");

printf("O numero %d foi repetido %d vezes\n", num, aux->cont);

}

}

void consultarDetalhes(no* raiz){

int num;

no* aux;

printf("Digite