Slides Estrutura de Dados Aula 04

Prévia do material em texto

Estrutura de Dados
Aula 04
Orlei José Pombeiro
Organização da Aula
� Nesta aula vamos praticar 
técnicas de ordenação e pesquisa:
• Ordenação por Inserção
• Ordenação por Seleção
• Pesquisa Sequencial
• Pesquisa Binária
FIM
Vídeo 1 – conversa inicial
Contextualização
Ordenação e Pesquisa
Vídeo 2 – Contextualização
Contextualização
8 16 34 13 19 7 45 3 12 9
• Ordenação
• Pesquisa Sequencial
• Pesquisa Binária
FIM
Ordenação por Inserção
Loop Troca 1º 2º 3º 4º 5º 6º 7º 8º 9º 10º
Vetor Inicial 8 16 34 13 19 7 45 3 12 9
1º 1º -> 6º 7 16 34 13 19 8 45 3 12 9
1º 1º -> 8º 3 16 34 13 19 8 45 7 12 9
2º 2º -> 4º 3 13 34 16 19 8 45 7 12 9
2º 2º -> 7º 3 8 34 16 19 13 45 7 12 9
2º 2º -> 8º 3 7 34 16 19 13 45 8 12 9
3º 3º -> 4º 3 7 16 34 19 13 45 8 12 9
3º 3º -> 6º 3 7 13 34 19 16 45 8 12 9
3º 3º -> 8º 3 7 8 34 19 16 45 13 12 9
Vídeo 3 – Tema 1
Ordenação por Inserção
Loop Troca 1º 2º 3º 4º 5º 6º 7º 8º 9º 10º
Vetor Inicial 8 16 34 13 19 7 45 3 12 9
4º 4º -> 5º 3 7 8 19 34 16 45 13 12 9
4º 4º -> 6º 3 7 8 16 34 19 45 13 12 9
4º 4º -> 8º 3 7 8 13 34 19 45 16 12 9
4º 4º -> 9º 3 7 8 12 34 19 45 16 13 9
4º 4º -> 10º 3 7 8 9 34 19 45 16 13 12
5º 5º -> 6º 3 7 8 9 19 34 45 16 13 12
5º 5º -> 8º 3 7 8 9 16 34 45 19 13 12
5º 5º -> 9º 3 7 8 9 13 34 45 19 16 12
5º 5º -> 10º 3 7 8 9 12 34 45 19 16 13
6º 6º -> 8º 3 7 8 9 12 19 45 34 16 13
6º 6º -> 9º 3 7 8 9 12 16 45 34 19 13
6º 6º -> 10º 3 7 8 9 12 13 45 34 19 16
Ordenação por Inserção
Loop Troca 1º 2º 3º 4º 5º 6º 7º 8º 9º 10º
Vetor Inicial 8 16 34 13 19 7 45 3 12 9
7º 7º -> 8º 3 7 8 9 12 13 34 45 19 16
7º 7º -> 9º 3 7 8 9 12 13 19 45 34 16
7º 7º -> 10º 3 7 8 9 12 13 16 45 34 19
8º 8º -> 9º 3 7 8 9 12 13 16 34 45 19
8º 8º -> 10º 3 7 8 9 12 13 16 19 45 34
9º 9º -> 10º 3 7 8 9 12 13 16 19 34 45
Vetor 
Ordenado
3 7 8 9 12 13 16 19 34 45
Ordenação por Inserção
main()
{ int vetor[10] = { 8, 16, 34, 13, 19, 7, 45, 3, 12, 9 };
int x, y, aux;
for(x=0; x<9; x++)
for(y=x+1; y<10; Y++)
if(vetor[x] < vetor[y])
{ aux = vetor[x];
vetor[x] = vetor[y];
vetor[y] = aux;
}
}
FIM
Ordenação por Seleção
8 16 34 13 19 7 45 3 12 9
Vídeo 4 – Tema 2
Ordenação por Seleção
Loop Troca 1º 2º 3º 4º 5º 6º 7º 8º 9º 10º
Vetor Inicial 8 16 34 13 19 7 45 3 12 9
1º 3º -> 4º 8 16 13 34 19 7 45 3 12 9
1º 4º -> 5º 8 16 13 19 34 7 45 3 12 9
1º 5º -> 6º 8 16 13 19 7 34 45 3 12 9
1º 7º -> 8º 8 16 13 19 7 34 3 45 12 9
1º 8º -> 9º 8 16 13 19 7 34 3 12 45 9
1º 9º -> 10º 8 16 13 19 7 34 3 12 9 45
2º 2º -> 3º 8 13 16 19 7 34 3 12 9 45
2º 4º -> 5º 8 13 16 7 19 34 3 12 9 45
2º 6º -> 7º 8 13 16 7 19 3 34 12 9 45
2º 7º -> 8º 8 13 16 7 19 3 12 34 9 45
2º 8º -> 9º 8 13 16 7 19 3 12 9 34 45
Ordenação por Seleção
Loop Troca 1º 2º 3º 4º 5º 6º 7º 8º 9º 10º
Vetor Inicial 8 16 34 13 19 7 45 3 12 9
3º 3º -> 4º 8 13 7 16 19 3 12 9 34 45
3º 5º -> 6º 8 13 7 16 3 19 12 9 34 45
3º 6º -> 7º 8 13 7 16 3 12 19 9 34 45
3º 7º -> 8º 8 13 7 16 3 12 9 19 34 45
4º 2º -> 3º 8 7 13 16 3 12 9 19 34 45
4º 4º -> 5º 8 7 13 3 16 12 9 19 34 45
4º 5º -> 6º 8 7 13 3 12 16 9 19 34 45
4º 6º -> 7º 8 7 13 3 12 9 16 19 34 45
Ordenação por Seleção
Loop Troca 1º 2º 3º 4º 5º 6º 7º 8º 9º 10º
Vetor Inicial 8 16 34 13 19 7 45 3 12 9
5º 1º -> 2º 7 8 13 3 12 9 16 19 34 45
5º 3º -> 4º 7 8 3 13 12 9 16 19 34 45
5º 4º -> 5º 7 8 3 12 13 9 16 19 34 45
5º 5º -> 6º 7 8 3 12 9 13 16 19 34 45
6º 2º -> 3º 7 3 8 12 9 13 16 19 34 45
6º 4º -> 5º 7 3 8 9 12 13 16 19 34 45
7º 1º -> 2º 3 7 8 9 12 13 16 19 34 45
Vetor 
Ordenado
3 7 8 9 12 13 16 19 34 45
Ordenação por Seleção
main()
{ int vetor[10] = { 8, 16, 34, 13, 19, 7, 45, 3, 12, 9 };
int x, aux;
char ch;
do
{ ch = ‘N’;
for(x=0; x<9; x++)
if(vetor[x] < vetor[x+1])
{ aux = vetor[x];
vetor[x] = vetor[x+1];
vetor[x+1] = aux;
ch = ‘S’;
}
} while(ch == ‘S’);
} FIM
Pesquisa Sequencial
1. Esta na 1ª posição? 
2. Esta na 2ª posição?
3. Esta na 3ª posição?
4. Esta na 4ª posição?
5. Esta na 5ª posição?
6. Esta na 6ª posição?
7. Esta na 7ª posição?
8. Esta na 8ª posição?
9. Esta na 9ª posição?
10.Esta na 10ª posição?
1º 2º 3º 4º 5º 6º 7º 8º 9º 10º 11º 12º 13º 14º 15º 16º
3 7 8 10 13 15 18 22 26 27 32 35 43 47 53 57
Pesquisar o 
número 27
Vídeo 5 – Tema 3
Pesquisa Sequencial
main()
{ int vetor[20] = { 3, 7, 8, 10, 13, 15, 18, 22, 26, 27, 32, 35, 43, 47, 53, 57, 62, 63, 72, 
84};
int x, aux;
printf(“Informe um valor para ser localizado no vetor: ”);
scanf(“%d”, aux);
for(x=0; x<20; x++)
if(vetor[x] == aux)
break;
if(x < 20)
printf(“O valor informado esta na posição %d do vetor.”, x);
else
printf(“O valor informado não esta no vetor.”);
} FIM
Pesquisa Binária
1ª Pesquisa:
1. Dividir o vetor ao meio.
2. Pesquisar a posição central “8º”
3. É o número desejado? Não.
4. Esta na metade inferior ou superior?
5. Repetir pesquisa.
1º 2º 3º 4º 5º 6º 7º 8º 9º 10º 11º 12º 13º 14º 15º 16º
3 7 8 10 13 15 18 22 26 27 32 35 43 47 53 57
Pesquisar o 
número 27
Vídeo 6 – Tema 4
Pesquisa Binária
2ª Pesquisa:
1. Dividir o sub vetor superior ao meio.
2. Pesquisar a posição central “12º”
3. É o número desejado? Não.
4. Esta na metade inferior ou superior?
5. Repetir pesquisa.
1º 2º 3º 4º 5º 6º 7º 8º 9º 10º 11º 12º 13º 14º 15º 16º
3 7 8 10 13 15 18 22 26 27 32 35 43 47 53 57
Pesquisar o 
número 27
Pesquisa Binária
3ª Pesquisa:
1. Dividir o sub vetor inferior ao meio.
2. Pesquisar a posição central “10º”
3. É o número desejado? Sim.
4. Fim da Pesquisa
1º 2º 3º 4º 5º 6º 7º 8º 9º 10º 11º 12º 13º 14º 15º 16º
3 7 8 10 13 15 18 22 26 27 32 35 43 47 53 57
Pesquisar o 
número 27
Pergunta: Qual o número máximo de pesquisas 
em um vetor de 1 milhão de posições utilizando 
pesquisa Sequencial e Binária? 
R.: Pesquisa Sequencial = 1.000.000 pesquisas
R.: Pesquisa Binária = 20 pesquisas
148576 / 2 = 524288
524288 / 2 = 262144
262144 / 2 = 131072
131072 / 2 = 65536
65536 / 2 = 31250
32768 / 2 = 16384
16384 / 2 = 8192
8192 / 2 = 4096
4096 / 2 = 2048
2048 / 2 = 1024
FIM
1024 / 2 = 512
512 / 2 = 256
256 / 2 = 128
128 / 2 = 64
64 / 2 = 32
32 / 2 = 12
16 / 2 = 8
8 / 2 = 4
4 / 2 = 2
2 / 2 = 1
Aplicação
Pesquisa e Ordenação
Vídeo 7 – Aplicação Prática
Aplicação
Vejamos o algoritmo da Pesquisa Binária utilizando 
Recursividade.
main()
{ int vetor[20] = { 3, 7, 8, 10, 13, 15, 18, 22, 26, 27, 32, 35, 43, 47, 53, 57, 62, 63, 72, 
84 };
int num, pos;
printf(“Informe um número para pesquisa: ”);
scanf(“%d”, &num);
pos = pesquisa_binaria(vetor, 0, 19, num);
if (pos == -1)
printf(“O número não esta na lista.”);
else
printf(“O número esta na posição %d da lista.”, pos);
}
pesquisa_binaria (int vet[], int inicio, int fim, int numero)
{ int pivo;
if (inicio > fim)
return (-1);
pivo = ((fim - inicio) / 2) + inicio;
if (numero > vet[pivo])
return ( pesquisa_binaria (vet, pivo+1, fim, numero) );
if (numero < vet[pivo])
return ( pesquisa_binaria (vet, inicio, pivo-1, numero) );
return (pivo);
}
FIM
Síntese
Pesquisa e Ordenação
Vídeo 8 – Síntese
Síntese
FIM
� O objetivo de ordenarmos 
bases de dados, é por 
conta da pesquisa da 
informação ser mais rápida.
� Embora mais complexos, 
algoritmos de Pesquisa 
Bin[ária são muito mais 
eficientes.
Referências de Apoio
•SCHILDT, Herbert; C Completo e Total, Ed. Person 
Education do Brasil, São Paulo, 1997
� https://programacaodescompl
icada.wordpress.com/indice/li
nguagem-c/