Métodos de Ordenação e Pesquisa em Javascript

Prévia do material em texto

ESTRUTURA DE DADOS
Aula 4 – Ordenação e Pesquisa
Prof. ANITA LOPES
Produzido em 2013
Prof. ANITA LOPES
Produzido em 2013
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;
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Recordando
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
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.
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Comparando vetores numéricos, ou char de um caracter
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
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().
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Comparando vetores de char
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
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().
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Comparando membros de structs
aux é uma struct do mesmo tipo que candidatos
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
O uso de struct simplifica muito, pois constatamos isso nesse trecho de troca.
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Muito bem observado. Não importa quantos membros tenha um vetor que só existirá um trecho de troca.
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Ordenação
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 indicados para conjuntos grandes;
 usam menos comparações;
 os códigos são grandes;
 alguns incluem conceito de recursividade, deixando-os mais complexos.
Exemplos:
Heap Sort(Ordenação por seleção em árvores) 
Shell Sort (Ordenação por inserção, vários segmentos)
Quick Sort(Ordenação por troca/partição)
Métodos Eficientes ou Sofisticados
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Selection Sort
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
13
23
3
8
1
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
0
13
23
3
8
1
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
0
13
23
3
8
1
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
0
13
23
3
8
1
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
0
13
23
3
8
1
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
0
13
23
3
8
1
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
2
13
23
3
8
1
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
2
13
23
3
8
1
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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;
 }
}
 MPDisplay
Teste de Mesa
0
1
2
3
4
3
0
2
13
23
3
8
1
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
2
13
23
3
8
1
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
2
13
23
3
8
1
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
4
13
23
3
8
1
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
13
23
3
8
1
Abandona o for
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
1
13
23
3
8
1
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
1
13
23
3
8
13
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
1
1
23
3
8
13
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
1
1
23
3
8
13
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
1
1
23
3
8
13
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
1
1
23
3
8
13
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
1
1
23
3
8
13
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
1
1
23
3
8
13
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
1
1
23
3
8
13
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
1
1
23
3
8
13
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
1
1
23
3
8
13
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
1
1
23
3
8
13
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
1
1
23
3
8
13
Abandona o for
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
3
1
23
3
8
13
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
3
1
23
23
8
13
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
3
1
3
23
8
13
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
3
1
3
23
8
13
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
3
1
3
23
8
13
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
3
1
3
23
8
13
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
3
1
3
23
8
13
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
3
1
3
23
8
13
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
3
1
3
23
8
13
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
3
1
3
23
8
13
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
3
1
3
23
8
13
Abandona o for
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
8
1
3
23
8
13
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
8
1
3
23
23
13
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
8
1
3
8
23
13
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
8
1
3
8
23
13
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
8
1
3
8
23
13
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
8
1
3
8
23
13
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
8
1
3
8
23
13
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
8
1
3
8
23
13
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
8
1
3
8
23
13
Abandona o for
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
13
1
3
8
23
13
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
13
1
3
8
23
23
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
13
1
3
8
13
23
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
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.
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Insertion Sort
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Insertion Sort
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Teste de Mesa
vet j i aux 
1
23
1
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Teste de Mesa
vet j i aux 
1
23
1
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Teste de Mesa
vet j i aux 
1
23
1
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Teste de Mesa
vet j i aux 
1
23
1
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Teste de Mesa
vet j i aux 
2
23
1
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Teste de Mesa
vet j i aux 
2
3
1
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Teste de Mesa
vet j i aux 
2
3
2
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Teste de Mesa
vet j i aux 
2
3
2
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Teste de Mesa
vet j i aux 
2
3
2
 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; 
 }
}
1323
23
8
1
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Teste de Mesa
vet j i aux 
2
3
1
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Teste de Mesa
vet j i aux 
2
3
1
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Teste de Mesa
vet j i aux 
2
3
1
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Teste de Mesa
vet j i aux 
2
3
0
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Teste de Mesa
vet j i aux 
2
3
0
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Teste de Mesa
vet j i aux 
3
3
0
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Teste de Mesa
vet j i aux 
3
8
0
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Teste de Mesa
vet j i aux 
3
8
3
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Teste de Mesa
vet j i aux 
3
8
3
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Teste de Mesa
vet j i aux 
3
8
3
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Teste de Mesa
vet j i aux 
3
8
2
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Teste de Mesa
vet j i aux 
3
8
2
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Teste de Mesa
vet j i aux 
3
8
2
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Teste de Mesa
vet j i aux 
3
8
1
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Teste de Mesa
vet j i aux 
3
8
1
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Teste de Mesa
vet j i aux 
3
8
1
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Teste de Mesa
vet j i aux 
3
8
1
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Teste de Mesa
vet j i aux 
4
8
1
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Teste de Mesa
vet j i aux 
4
1
1
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Teste de Mesa
vet j i aux 
4
1
4
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Teste de Mesa
vet j i aux 
4
1
4MP 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Teste de Mesa
vet j i aux 
4
1
4
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Teste de Mesa
vet j i aux 
4
1
3
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Teste de Mesa
vet j i aux 
4
1
3
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Teste de Mesa
vet j i aux 
4
1
3
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Teste de Mesa
vet j i aux 
4
1
2
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Teste de Mesa
vet j i aux 
4
1
2
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Teste de Mesa
vet j i aux 
4
1
2
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Teste de Mesa
vet j i aux 
4
1
1
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Teste de Mesa
vet j i aux 
4
1
1
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Teste de Mesa
vet j i aux 
4
1
1
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Teste de Mesa
vet j i aux 
4
1
0
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Teste de Mesa
vet j i aux 
4
1
0
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Teste de Mesa
vet j i aux 
4
1
0
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Teste de Mesa
vet j i aux 
5
1
0
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
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.
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
APLICAÇÃO
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
APLICAÇÃO
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
APLICAÇÃO
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
APLICAÇÃO
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
APLICAÇÃO
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
APLICAÇÃO
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
APLICAÇÃO
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
APLICAÇÃO
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
APLICAÇÃO
APLICAÇÃO
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
APLICAÇÃO
APLICAÇÃO
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Código
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; 
 }
}
#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");
}
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Bubble Sort
O princípiobásico desse método é trocar de posições todas vezes que forem encontrados valores de posições adjacentes fora de ordem.
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Bubble Sort
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
13
23
3
8
1
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
13
23
3
8
1
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
13
23
3
8
1
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
1
13
23
3
8
1
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
1
13
23
3
8
8
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
1
13
23
3
1
8
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
1
13
23
3
1
8
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
1
13
23
3
1
8
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
1
13
23
3
1
8
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
1
13
23
3
3
8
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
1
13
23
1
3
8
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
1
13
23
1
3
8
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
1
13
23
1
3
8
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
1
13
23
1
3
8
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
1
13
23
23
3
8
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
1
13
1
23
3
8
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
1
13
1
23
3
8
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
1
13
1
23
3
8
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
1
13
1
23
3
8
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
1
13
13
23
3
8
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
1
1
13
23
3
8
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
1
1
13
23
3
8
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
1
1
13
23
3
8
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
1
1
13
23
3
8
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
1
1
13
23
3
8
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
1
1
13
23
3
8
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
1
1
13
23
3
8
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
3
1
13
23
3
8
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
3
1
13
23
23
8
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
3
1
13
3
23
8
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
3
1
13
3
23
8
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
3
1
13
3
23
8
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
3
1
13
3
23
8
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
3
1
13
13
23
8
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
3
1
3
13
23
8
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
3
1
3
13
23
8
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
3
1
3
13
23
8
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
3
1
3
13
23
8
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
8
1
3
13
23
8
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
8
1
3
13
23
23
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
8
1
3
13
8
23
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
8
1
3
13
8
23
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
8
1
3
13
8
23
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
8
1
3
13
8
23
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
8
1
3
13
13
23
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
8
1
3
8
13
23
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
8
1
3
8
13
23
Abandona o for
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
8
1
3
8
13
23
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
8
1
3
8
13
23
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
8
1
3
8
13
23
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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
8
1
3
8
13
23
Abandona o for
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
 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 Mesa0
1
2
3
4
3
4
8
Finaliza
1
3
8
13
23
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Uma informação importante a saber
 É o mais conhecido método.
 Simples.
 Muito lento.
 É considerado o pior dos três estudados.
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Pesquisa
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
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.
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
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
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
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; 
}
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
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.
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
SEQUENCIAL OU BINÁRIA?
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Se ordenado, BINÁRIA.
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013
Espero que goste
Prof. ANITA LOPES
Produzido em 2012
Prof. ANITA LOPES
Produzido em 2013