Aula 04 Ordenação e Pesquisa

Prévia do material em texto

ESTRUTURA DE DADOS
Aula 4 – Ordenação e Pesquisa
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Atenção aos Temas Principais dessa Aula
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Conteúdo Programático desta aula
Compreender e usar o método de ordenação
insertion sort, (inserção);
Compreender e usar o método de ordenação
selection sort (seleção);
Compreender e usar o método de ordenação
bubble sort(bolha);
Compreender e usar o método de pesquisa
sequencial;
Compreender e usar o método de pesquisa binária;
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Direto ao Assunto
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Comparando vetores numéricos, ou char de um caracter
Para comparar vetores numéricos, ou char de um caracter,
usamos os operadores relacionais >, >=, <, <= , == e !=.
Para trocar os conteúdos das variáveis, usamos o comando
de atribuição.
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Comparando vetores numéricos, ou char de um caracter
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Comparando vetores de char
Para compararmos vetores de char, usaremos a função
strcmp().
Para copiarmos o conteúdo de um vetor de char nas
posições ocupadas por outro vetor de char,usaremos a
função strcpy().
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Comparando vetores de char
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Comparando membros de structs
Para comparar membros de structs, procedermos da
seguinte maneira:
 Numéricos ou char de um caracter: >, >=, <, <= , == e
!= e, para trocar os conteúdos das variáveis, o comando de
atribuição.
 Vetor de char: strcmp() e strcpy().
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Comparando membros de structs
aux é uma struct do mesmo tipo que candidatos
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
O uso de struct simplifica muito,
pois constatamos isso nesse trecho
de troca.
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Muito bem observado. Não importa
quantos membros tenha um vetor
que só existirá um trecho de troca.
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
• mais eficientes para para pequenos conjuntos;
• usam muitas comparações;
• códigos pequenos;
• códigos de fácil entendimento; 
Exemplos:
1. Selection Sort(Ordenação por seleção)
2. Insertion Sort(Ordenação por inserção)
3. Bubble Sort (Ordenação por troca)
Métodos Simples
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
• indicados para conjuntos grandes;
• usam menos comparações;
• os códigos são grandes;
• alguns incluem conceito de recursividade, deixando-os
mais complexos.
Exemplos:
1. Heap Sort(Ordenação por seleção em árvores)
2. Shell Sort (Ordenação por inserção, vários segmentos)
3. Quick Sort(Ordenação por troca/partição)
Métodos Eficientes ou Sofisticados
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
O princípio básico desse método é
sempre buscar o menor dos valores
restantes e levá-lo às posições
iniciais(ordenação crescente).
Selection Sort
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
O princípio básico desse método é
sempre buscar o menor dos valores
restantes e levá-lo às posições
iniciais(ordenação crescente).
Selection Sort
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Selection Sort
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
13
23
3
8
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
013
23
3
8
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
0 013
23
3
8
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
1 0 013
23
3
8
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
1 0 013
23
3
8
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
2 0 013
23
3
8
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
2 0 013
23
3
8
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
2 0 213
23
3
8
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
3 0 213
23
3
8
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
3 0 213
23
3
8
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
4 0 213
23
3
8
1
ESTRUTURADE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
4 0 213
23
3
8
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
4 0 413
23
3
8
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
5 0 413
23
3
8
1
Abandona o for
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
5 0 4 113
23
3
8
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
5 0 4 113
23
3
8
13
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
5 0 4 11
23
3
8
13
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
5 0 4 11
23
3
8
13
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
5 1 4 11
23
3
8
13
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
5 1 1 11
23
3
8
13
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
2 1 1 11
23
3
8
13
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
2 1 2 11
23
3
8
13
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
3 1 2 11
23
3
8
13
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
3 1 2 11
23
3
8
13
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
4 1 2 11
23
3
8
13
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
4 1 2 11
23
3
8
13
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
5 1 2 11
23
3
8
13
Abandona o for
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
5 1 2 31
23
3
8
13
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
5 1 2 31
23
23
8
13
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
5 1 2 31
3
23
8
13
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}MP Display
Teste de Mesa
0
1
2
3
4
5 2 2 31
3
23
8
13
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
5 2 2 31
3
23
8
13
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
3 2 2 31
3
23
8
13
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
3 2 2 31
3
23
8
13
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
3 2 3 31
3
23
8
13
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
4 2 3 31
3
23
8
13
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
4 2 3 31
3
23
8
13
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
5 2 3 31
3
23
8
13
Abandona o for
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
5 2 3 81
3
23
8
13
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
5 2 3 81
3
23
23
13
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
5 2 3 81
3
8
23
13
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
5 3 3 81
3
8
23
13
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
5 3 3 81
3
8
23
13
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
4 3 3 81
3
8
23
13
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
4 3 3 81
3
8
23
13
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
4 3 4 81
3
8
23
13
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
5 3 4 81
3
8
23
13
Abandona o for
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
5 3 4 131
3
8
23
13
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
5 3 4 131
3
8
23
23
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1; i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
5 3 4 131
3
8
13
23
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux temp
void selecao(int vet[], int tam)
{ int j, i, aux,temp;
for ( i=0; i<tam -1;i++)
{ aux = i;
for(j=i+1; j<tam; j++)
if(vet[aux] > vet[j] ) aux=j;
temp=vet[aux];
vet[aux]= vet[i];
vet[i]=temp;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
5 4 4 13
Finaliza
1
3
8
13
23
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Uma informação importante a saber
• O primeiro passo é selecionar o menor valor da lista, se
for uma ordenação crescente, armazenando sua posição.
• Depois de verificar todos os elementos, o valor que esse
encontra na posição indicada, será trocado com o valor da
primeira posição.
• Esse processo se repete até que a ordenação esteja
completa, mas sempre buscando o menor.
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
O princípio básico desse
método é considerar o
vetor como dois
subvetores, um ordenado e
o outro, desordenado,
buscando posicionar o
elemento que se encontra
no subvetor desordenado,
no vetor ordenado.
Insertion Sort
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
O princípio básico desse
método é considerar o
vetor como dois
subvetores, um ordenado e
o outro, desordenado,
buscando posicionar o
elemento que se encontra
no subvetor desordenado,
no vetor ordenado.
Insertion Sort
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Insertion Sort
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Insertion Sort
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
1
Teste de Mesa
MP Display
0
1
2
3
4
void insercao(int vet[], int tam)
{
int j,i, aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux <vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
13
23
3
8
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
1 23
Teste de Mesa
MP Display
0
1
2
3
4
void insercao(int vet[], int tam)
{
int j,i, aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux <vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
13
23
3
8
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Teste de Mesa
vet j i aux 
1 231
MP Display
0
1
2
3
4
void insercao(int vet[], int tam)
{
int j,i, aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux <vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
13
23
3
8
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Teste de Mesa
vet j i aux 
1 231
MP Display
0
1
2
3
4
void insercao(int vet[], int tam)
{
int j,i, aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux <vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
13
23
3
8
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Teste de Mesa
vet j i aux 
1 231
MP Display
0
1
2
3
4
void insercao(int vet[], int tam)
{
int j,i, aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux <vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
13
23
3
8
1
Abandona o for
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Teste de Mesa
vet j i aux 
1 231
MP Display
0
1
2
3
4
void insercao(int vet[], int tam)
{
int j,i, aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux <vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
13
23
3
8
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Teste de Mesa
vet j i aux 
2 231
MP Display
0
1
2
3
4
void insercao(int vet[], int tam)
{
int j,i, aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux <vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
13
23
3
8
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Teste de Mesa
vet j i aux 
2 31
MP Display
0
1
2
3
4
void insercao(int vet[], int tam)
{
int j,i, aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux <vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
13
23
3
8
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Teste de Mesa
vet j i aux 
2 32
MP Display
0
1
2
3
4
void insercao(int vet[], int tam)
{
int j,i, aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux <vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
13
23
3
8
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Teste de Mesa
vet j i aux 
2 32
MP Display
0
1
2
3
4
void insercao(int vet[], int tam)
{
int j,i, aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux <vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
13
23
3
8
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Teste de Mesa
vet j i aux 
2 32
MP Display
0
1
2
3
4
void insercao(int vet[], int tam)
{
int j,i, aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux <vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
13
23
23
8
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Teste de Mesa
vet j i aux 
2 31
MP Display
0
1
2
3
4
void insercao(int vet[], int tam)
{
int j,i, aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux <vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
13
23
23
8
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Teste de Mesa
vet j i aux 
2 31
MP Display
0
1
2
3
4
void insercao(int vet[], int tam)
{
int j,i, aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux <vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
13
23
23
8
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Teste de Mesa
vet j i aux 
2 31
MP Display
0
1
2
3
4
void insercao(int vet[], int tam)
{
int j,i, aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux <vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
13
13
23
8
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Teste de Mesa
vet j i aux 
2 30
MP Display
0
1
2
3
4
void insercao(int vet[], int tam)
{
int j,i, aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux <vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
13
13
23
8
1
Abandona o for
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Teste de Mesa
vet j i aux 
2 30
MP Display
0
1
2
3
4
void insercao(int vet[], int tam)
{
int j,i, aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux <vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
3
13
23
8
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Teste de Mesa
vet j i aux 
3 30
MP Display
0
1
2
3
4
void insercao(int vet[], int tam)
{
int j,i, aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux <vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
3
13
23
8
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Teste de Mesa
vet j i aux 
3 80
MP Display
0
1
2
3
4
void insercao(int vet[], int tam)
{
int j,i, aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux <vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
3
13
23
8
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Teste de Mesavet j i aux 
3 83
MP Display
0
1
2
3
4
void insercao(int vet[], int tam)
{
int j,i, aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux <vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
3
13
23
8
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Teste de Mesa
vet j i aux 
3 83
MP Display
0
1
2
3
4
void insercao(int vet[], int tam)
{
int j,i, aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux <vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
3
13
23
8
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Teste de Mesa
vet j i aux 
3 83
MP Display
0
1
2
3
4
void insercao(int vet[], int tam)
{
int j,i, aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux <vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
3
13
23
23
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Teste de Mesa
vet j i aux 
3 82
MP Display
0
1
2
3
4
void insercao(int vet[], int tam)
{
int j,i, aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux <vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
3
13
23
23
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Teste de Mesa
vet j i aux 
3 82
MP Display
0
1
2
3
4
void insercao(int vet[], int tam)
{
int j,i, aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux <vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
3
13
23
23
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Teste de Mesa
vet j i aux 
3 82
MP Display
0
1
2
3
4
void insercao(int vet[], int tam)
{
int j,i, aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux <vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
3
13
13
23
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Teste de Mesa
vet j i aux 
3 81
MP Display
0
1
2
3
4
void insercao(int vet[], int tam)
{
int j,i, aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux <vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
3
13
13
23
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Teste de Mesa
vet j i aux 
3 81
MP Display
0
1
2
3
4
void insercao(int vet[], int tam)
{
int j,i, aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux <vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
3
13
13
23
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Teste de Mesa
vet j i aux 
3 81
MP Display
0
1
2
3
4
void insercao(int vet[], int tam)
{
int j,i, aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux <vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
3
13
13
23
1
Abandona o for
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Teste de Mesa
vet j i aux 
3 81
MP Display
0
1
2
3
4
void insercao(int vet[], int tam)
{
int j,i, aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux <vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
3
8
13
23
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Teste de Mesa
vet j i aux 
4 81
MP Display
0
1
2
3
4
void insercao(int vet[], int tam)
{
int j,i, aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux <vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
3
8
13
23
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Teste de Mesa
vet j i aux 
4 11
MP Display
0
1
2
3
4
void insercao(int vet[], int tam)
{
int j,i, aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux <vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
3
8
13
23
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Teste de Mesa
vet j i aux 
4 14
MP Display
0
1
2
3
4
void insercao(int vet[], int tam)
{
int j,i, aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux <vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
3
8
13
23
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Teste de Mesa
vet j i aux 
4 14
MP Display
0
1
2
3
4
void insercao(int vet[], int tam)
{
int j,i, aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux <vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
3
8
13
23
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Teste de Mesa
vet j i aux 
4 14
MP Display
0
1
2
3
4
void insercao(int vet[], int tam)
{
int j,i, aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux <vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
3
8
13
23
23
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Teste de Mesa
vet j i aux 
4 13
MP Display
0
1
2
3
4
void insercao(int vet[], int tam)
{
int j,i, aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux <vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
3
8
13
23
23
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Teste de Mesa
vet j i aux 
4 13
MP Display
0
1
2
3
4
void insercao(int vet[], int tam)
{
int j,i, aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux <vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
3
8
13
23
23
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Teste de Mesa
vet j i aux 
4 13
MP Display
0
1
2
3
4
void insercao(int vet[], int tam)
{
int j,i, aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux <vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
3
8
13
13
23
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Teste de Mesa
vet j i aux 
4 12
MP Display
0
1
2
3
4
void insercao(int vet[], int tam)
{
int j,i, aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux <vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
3
8
13
13
23
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Teste de Mesa
vet j i aux 
4 12
MP Display
0
1
2
3
4
void insercao(int vet[], int tam)
{
int j,i, aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux <vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
3
8
13
13
23
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Teste de Mesa
vet j i aux 
4 12
MP Display
0
1
2
3
4
void insercao(int vet[], int tam)
{
int j,i, aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux <vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
3
8
8
13
23
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Teste de Mesa
vet j i aux 
4 11
MP Display
0
1
2
3
4
void insercao(int vet[], int tam)
{
int j,i, aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux <vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
3
8
8
13
23
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Teste de Mesa
vet j i aux 
4 11
MP Display
0
12
3
4
void insercao(int vet[], int tam)
{
int j,i, aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux <vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
3
8
8
13
23
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Teste de Mesa
vet j i aux 
4 11
MP Display
0
1
2
3
4
void insercao(int vet[], int tam)
{
int j,i, aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux <vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
3
3
8
13
23
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Teste de Mesa
vet j i aux 
4 10
MP Display
0
1
2
3
4
void insercao(int vet[], int tam)
{
int j,i, aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux <vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
3
3
8
13
23
Abandona o for
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Teste de Mesa
vet j i aux 
4 10
MP Display
0
1
2
3
4
void insercao(int vet[], int tam)
{
int j,i, aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux <vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
1
3
8
13
23
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Teste de Mesa
vet j i aux 
4 10
MP Display
0
1
2
3
4
void insercao(int vet[], int tam)
{
int j,i, aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux <vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
1
3
8
13
23
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Teste de Mesa
vet j i aux 
5 10
MP Display
0
1
2
3
4
void insercao(int vet[], int tam)
{
int j,i, aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux <vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
Finaliza
1
3
8
13
23
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Uma informação importante a saber
• Só ordena quando necessário.
• Quando um elemento é inserido no vetor ordenado,
todos os elementos maiores do que ele, são deslocados
para a direita(nessa explicação, para baixo, mas o
resultado é o mesmo).
•É considerado o melhor dos três métodos estudados.
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
APLICAÇÃO
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
APLICAÇÃO
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
APLICAÇÃO
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
APLICAÇÃO
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
APLICAÇÃO
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
APLICAÇÃO
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
APLICAÇÃO
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
APLICAÇÃO
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
APLICAÇÃOAPLICAÇÃO
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
APLICAÇÃOAPLICAÇÃO
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Código
void insercao(dados vet[], int tam)
{
int j,i; dados aux;
for (i=1;i<tam;i++)
{ aux = vet[i];
for(j=i; j>0 && aux.CR <vet[j-1].CR; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}
}
#include<iostream>
#include<cstdlib>
using namespace std;
struct dados
{ int matric;
float CR;
};
void insercao(dados vetor[], int tam);
int main()
{
dados vet[]={13,9.5, 23, 10, 19 , 3};
system("cls");
cout<<"\nAntes da chamada da Funcao - INSERCAO\n";
for(int x=0; x<3;x++)
cout <<"\n"<<vet[x].matric<<"\t"<<vet[x].CR;
cout<<"\n";
insercao(vet, 3);
cout<<"\n\nDepois da chamada da Funcao -
INSERCAO\n";
for(int x=0; x<3;x++)
cout <<"\n"<<vet[x].matric<<"\t"<<vet[x].CR;
cout<<"\n\n"; system("pause");
}
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Bubble Sort
O princípio básico desse método é
trocar de posições todas vezes que
forem encontrados valores de posições
adjacentes fora de ordem.
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
O princípio básico desse método é
trocar de posições todas vezes que
forem encontrados valores de posições
adjacentes fora de ordem.
Bubble Sort
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Bubble Sort
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
13
23
3
8
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
013
23
3
8
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
4 013
23
3
8
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
4 013
23
3
8
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
4 0 113
23
3
8
1
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
4 0 113
23
3
8
8
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
4 0 113
23
3
1
8
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
3 0 113
23
3
1
8
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
3 0 113
23
3
1
8
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;}
}
MP Display
Teste de Mesa
0
1
2
3
4
3 0 113
23
3
1
8
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
3 0 113
23
3
3
8
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
3 0 113
23
1
3
8
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
2 0 113
23
1
3
8
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
2 0 113
23
1
3
8
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
2 0 113
23
1
3
8
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
2 0 113
23
23
3
8
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
2 0 113
1
23
3
8
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
1 0 113
1
23
3
8
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
1 0 113
1
23
3
8
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
1 0 113
1
23
3
8
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
1 0 113
13
23
3
8
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
1 0 11
13
23
3
8
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
1 0 11
13
23
3
8
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
0 0 1
Abandona o for
1
13
23
3
8
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
0 1 11
13
23
3
8
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
4 1 11
13
23
3
8
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
4 1 11
13
23
3
8
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
3 1 11
13
23
3
8
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
3 1 11
13
23
3
8
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
3 1 31
13
23
3
8
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
3 1 31
13
23
23
8
ESTRUTURA DE DADOS
ORDENAÇÃOE PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
3 1 31
13
3
23
8
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
2 1 31
13
3
23
8
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
2 1 31
13
3
23
8
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
2 1 31
13
3
23
8
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
2 1 31
13
13
23
8
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
2 1 31
3
13
23
8
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
1 1 3
Abandona o for
1
3
13
23
8
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
1 2 31
3
13
23
8
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
4 2 31
3
13
23
8
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
4 2 31
3
13
23
8
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
4 2 81
3
13
23
8
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
4 2 81
3
13
23
23
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
4 2 81
3
13
8
23
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
3 2 81
3
13
8
23
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
3 2 81
3
13
8
23
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
3 2 81
3
13
8
23
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
3 2 81
3
13
13
23
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
3 2 81
3
8
13
23
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
2 2 81
3
8
13
23
Abandona o for
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
2 3 81
3
8
13
23
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
4 3 81
3
8
13
23
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1;j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
4 3 81
3
8
13
23
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
3 3 81
3
8
13
23
Abandona o for
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
vet j i aux 
void bolha(int vet[], int tam)
{
int j,i, aux;
for (i=0; i<tam -1; i++)
for(j=tam-1; j>i; j--)
if(vet[j] < vet[j-1] )
{
aux=vet[j];
vet[j]= vet[j-1];
vet[j-1]=aux;
}
}
MP Display
Teste de Mesa
0
1
2
3
4
3 4 8
Finaliza
1
3
8
13
23
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Uma informação importante a saber
• É o mais conhecido método.
• Simples.
• Muito lento.
• É considerado o pior dos três estudados.
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
cout<<"\n...? ";
cin>>varProcura;
achou=0;
for(L=0;L<tamLinha && achou==0;L++)
{
if(varProcura==vetor[L])
{
achou=1; posicao=L;
}
}
if(achou==1)
cout<<"\n...: "<<outroVetor[posicao]<<endl;
else
cout<<"\nDado nao achado\n";
S
E
Q
U
E
N
C
I
A
L
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Uma informação importante a saber
• O vetor não precisa estar ordenado logo.
•A busca é mais simples porque percorre-se o vetor pelo
índice(deslocamento).
•O melhor caso é quando o elemento procurado se
encontra na primeira posição e o pior, na última.
• Retorna a posição do elemento quando encontrado.
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
cout<<"\n...? ";
cin>>procura;
inicio=0;
fim= tamanho - 1;
meio=(inicio+fim)/2;
while(procura != nomeVetor[meio] && inicio != fim)
{
if(procura > nomeVetor[meio]) inicio=meio+1;
else fim=meio;
meio=(inicio+fim)/2;
}
if(nomeVetor[meio]==procura)
cout<<"\n....: "<<outroVetor[meio]<<endl;
else
cout<<"\nDado nao encontrado\n";
B
I
N
Á
R
I
A
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
inicio=0;
fim= tamanho - 1;
meio=(inicio+fim)/2;
while(procura != nomeVetor[meio] && inicio != fim)
{
if(procura > nomeVetor[meio]) inicio=meio+1;
else fim=meio;
meio=(inicio+fim)/2;
}
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Uma informação importante a saber
• O vetor tem que estar ordenado.
• Divide-se, sucessivamente, o vetor ao meio, comparando
o elemento procurado com o elemento que se encontra na
posição central, descartando metade do vetor.
• É mais eficiente do que a busca sequencial.
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
SEQUENCIAL OU BINÁRIA?
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Se ordenado, BINÁRIA.
ESTRUTURA DE DADOS
ORDENAÇÃO E PESQUISA– Aula4
Resumindo