00.BubbleSort

Prévia do material em texto

Bolha: Estratégia
Estratégia
Faça uma analogia com uma taça de Champagne, qual o movimento das bolhas
Como o líquido “é ordenado” na 
taça?
Percorrer o vetor subindo (ou descendo) com as “bolhas”, elementos menores (ou maiores)
Curiosidade
Em que momentos temos os “estalos” para a solução de um problema?
Bolha: Simulação 
Passando várias vezes pelo
vetor, até a posição para onde 
a bolha deve ir
No segundo vetor, a “bolha” foi o 6
No quarto vetor, a “bolha” foi o 4
Perceba que a cada passagem,
a parte ordenada avança do fim
em direção ao início
Não é necessário passar por 
todo o conjunto de chaves,
apenas até a parte desordenada
Bolha: Simulação
Para subida da “bolha”, em cada 
passagem há uma comparação
com seus vizinhos
Se estiverem fora de ordem, o 
elemento for maior que o vizinho,
ocorre a troca
Na simulação ao lado
Na posição inicial não houve troca,
pois 5 é menor que 6
Nas outras posições o 6 sempre 
era maior que o elemento a direita
por isso a troca
Ao final da passagem, o elemento 
maior (6) ficou em sua posição
Bolha: Pseudocódigo
Ao analisar a lógica do método bolha as
seguintes partes da lógica podem
ser resumidas
Considerando a “casa alvo” da folha 
do final para o início
Para cada casa do vetor do início 
para o fim
Compare com o vizinho 
Quando for maior, realize troca
A
B
C
D
Bolha: Código em C
Implementação em linguagem C
A
B
C
D
Bolha: Conclusões
Análise da performance	
Ordem de complexidade O (n2)	- Quadrático
Vantagens
Fácil compreensão e implementação
Desvantagens
Ordem de complexidade alta
Para exemplificar, isso quer dizer que 
Para 100 números, 
o esforço é equivalente a 10000 operações
Outros algortimos possuem O (n log n)
O esforço seria aproximadamente de 600 para o mesmo caso acima