ATPS - Classificação e Pesquisa

Relação Reflexiva: Uma relação R é reflexiva se todo elemento de A está relacionado consigo mesmo, ou seja, para todo x[pic 1]A: (x,x)[pic 2]R, isto é, para todo x[pic 3]A: xRx. Exemplo: Uma relação reflexiva em A={1,2,3}, é dada por: R = {(1,1),(2,2),(3,3)}

Relação Simétrica: Uma relação R é simétrica se o fato que x está relacionado com y, implicar necessariamente que y está relacionado com x, ou seja: quaisquer que sejam x[pic 4]A e y[pic 5]A tal que (x,y)[pic 6]R, segue que (y,x)[pic 7]R. Exemplo: Uma relação simétrica em A={1,2,3}, é: R = {(1,1),(2,2),(1,2),(2,1)}

Relação Transitiva: Uma relação R é transitiva, se x está relacionado com y e y está relacionado com z, implicar que x deve estar relacionado com z, ou seja: quaisquer que sejam x[pic 8]A, y[pic 9]A e z[pic 10]A, se (x,y)[pic 11]R e (y,z)[pic 12]R então (x,z)[pic 13]R. Exemplo: Uma relação transitiva em A={1,2,3}, é: R = {(1,1),(1,3),(3,2),(1,2)}

Se A é o conjunto de todas as vagas existentes no 1º andar, E seria do 2° andar, I do 3° andar, O do 4° andar e U do 5° andar e cada elemento dos conjuntos representa uma vaga, cada andar tem 24 vagas.

Conjuntos A, E, I, O E U

A = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24)

E = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24)

I = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24)

O = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24)

U = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24)

Analisando os conjuntos podemos ver que há os três tipos de relações entre eles, sendo assim ela é uma relação de Equivalência.

Relações nos conjuntos A, E, I, O e U:

Reflexiva: (2,2)

Simétrica: (5,6) , (6,5)

Transitiva: (5,14) , (14,22), logo (5,22) pertence a relação.  

BUBBLESORT

Tamanho do Vetor	Trocas	Comparações	Tempo Gasto
500	26401	124750	0.01  Milissegundos
5000	1519304	12497500	0.7 Milissegundos
50000	133734425	1249975000	6.07 Segundos

SHELLSORT

Tamanho do Vetor	Trocas	Comparações	Tempo Gasto
500	13507	5964	0  Milissegundos
5000	82228	107312	0.01  Milissegundos
50000	1239226	1684945	0.1 Milissegundos

QUICKSORT

Tamanho do Vetor	Trocas	Comparações	Tempo Gasto
500	2290854	16857238	0  Milissegundos
5000	2274116	3276	0  Milissegundos
50000	9064	2123773	0.11 Milissegundos

BUSCA BINARIA

Tamanho do Vetor	Numero Buscado	Comparações	Tempo Gasto
500	150	9	0  Milissegundos
5000	523	12	0  Milissegundos
50000	1598	15	0  Milissegundos

• BubbleSort (500)

#include
#include
#define MAX 100000

void troca(int *a, int *b)
{
 int aux = *a;
 *a = *b ;
 *b = aux ;
}
void MostraHora()
{
struct tm *local;
time_t t;
t = time(NULL);
local=localtime(&t);
printf("%d:%d:%d\n",local->tm_hour,local->tm_min,local->tm_sec);
}
int BubbleSort(int *vetor, int tamanho, int *numeroTroca, int *comparacoes)
{
 int i,j;
 int ContadorTroca, ContadorComparacoes;
 for (i=tamanho-1; i>0; i--)
 {
   for (j=0; j    {
     ContadorComparacoes+=1;
     *comparacoes = ContadorComparacoes;
     if (vetor[i] < vetor[j])
     {
       troca(&vetor[i],&vetor[j]);
       ContadorTroca+=1;
       *numeroTroca = ContadorTroca ;
     }
   }
 }
}
void PreencherVetor(int *vetor, int tamanho){
    int contador = 0;
    for(contador; contador < tamanho; contador++)
    {
       vetor[contador] = rand() % tamanho;
    }
}
int main()
{
 clock_t t0, tf;
 double tempo_gasto;
 int v[500];
 PreencherVetor(v,500);
 int Comparacoes, Ntroca;
  t0 = clock();
 BubbleSort(v,500,&Ntroca,&Comparacoes);
 tf = clock();
 tempo_gasto = ( (double) (tf - t0) ) / CLOCKS_PER_SEC;
  printf("\n\nNumero de Trocas:      %d \n", Ntroca);
 printf("Numero de Comparacoes: %d \n", Comparacoes);
 printf("Tempo gasto:           %lf s\n", tempo_gasto);
  getch();  
}