passo 4 classificação e pesquisa
Esse trabalho consistiu em implementar a inserção direta e a inserção direta com busca binária, no sentido de analisar o custo de cada algoritmo assim como seu custo assintótico. Em ambos algoritmos foram utilizados dados de entrada do tipo float, e na inserção direta com busca binária foi usado o comando de memmov, cuja finalidade é copiar um certo tamanho de um bloco de dados a partir de um endereço para um outro endereço de destino. O código utilizado para realizar esse trabalho foi:
#include stdio.h #include stdlib.h #include time.h #include string.h void class_direta(float *vet, int n); void class_inicio_direta_bin(float *vet1,int n); void main () { int i,sinal,n; float *vet,*vet1; clock_t inicio,fim; srand (time(NULL)); n=2;
while ((n>1)) { printf ("Deseja inserir quantos?"); scanf ("%i",&n); n++; vet=malloc (n*sizeoffloat)); /*vetor q será ordenado na inserçaõ direta*/
vet1=malloc (n*sizeof(float)); /
for (i=1;i {vet[i]= rand () % 100000; Etapa 1 vet1[i]=vet[i];}
inicio= clock(); class_direta(vet,n); Etapa 2 fim= clock(); printf("\nTempo 1: %.0f milisegundos",((fim-inicio)/CLK_TCK)*1000);
inicio= clock(); class_inicio_direta_bin(vet1,n); fim= clock(); Etapa 3 printf("\nTempo 2: %.0f milisegundos\n",((fim-inicio)/CLK_TCK)*1000);}
} void class_direta(float *vet,int n) { int j,i; int chave;
for (j=1;j { chave=*(vet+j+1); Procedimento 1 i=j; while (i>=1 && *(vet+i)>chave) { *(vet+i+1)=*(vet+i); i=i-1; } *(vet+i+1)=chave; } }
void class_inicio_direta_bin(float *vet1,int n) { int inf=1,sup=2; int i,pivo,chave;
for (i=1;i { chave=vet1[i+1]; inf=1; sup=i; while (sup!=inf) { pivo = (inf + sup)/2; if (vet1[pivo]>=chave) Procedimento 2 sup=pivo; else {inf=pivo+1;} }
if (vet1[inf]>chave) {memmove (&vet1[inf+1],&vet1[inf],(i-inf+1)*sizeof(int)); vet1[inf]=chave;} else {memmove(&vet1[inf+2],&vet1[inf+1],(i-inf)*sizeof(int)); vet1[inf+1]=chave;} } }
O algoritmo Como já foi