Aula 5 Bubble Sort Melhorado

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

FEMAR - FUNDAÇÃO EDUCACIONAL DE MARIANA 
FAMA - FACULDADE DE ADMINISTRAÇÃO DE MARIANA 
Métodos de ordenação 
Bubble Sort 
Estrutura de Dados 
Professor: 
Ronan Loschi R. ferreira - ronan.loschi@gmail.com 
FEMAR - FUNDAÇÃO EDUCACIONAL DE MARIANA 
FAMA - FACULDADE DE ADMINISTRAÇÃO DE MARIANA 
Bubble Sort (Método Bolha): 
• Complexidade do método (comparações):
 Melhor caso: O(n). Pior caso: O(n²). 
• Vantagens:
 Simples 
 Estável 
 O fato de o vetor já estar ordenado ajuda a reduzir o número de 
comparações 
• Desvantagens:
 No pior caso o custo continua quadrático. 
FEMAR - FUNDAÇÃO EDUCACIONAL DE MARIANA 
FAMA - FACULDADE DE ADMINISTRAÇÃO DE MARIANA 
Bubble Sort (Método Bolha): 
SIMULAÇÃO 
FEMAR - FUNDAÇÃO EDUCACIONAL DE MARIANA 
FAMA - FACULDADE DE ADMINISTRAÇÃO DE MARIANA 
1ª vez: 
Truca := true 
N – 1 Comparações 
FEMAR - FUNDAÇÃO EDUCACIONAL DE MARIANA 
FAMA - FACULDADE DE ADMINISTRAÇÃO DE MARIANA 
2ª vez: 
N – 1 Comparações 
Truca := true 
OK! Vetor já ORDENAO! 
Vet[5] = {10, 21, 25, 30, 35, 80} 
FEMAR - FUNDAÇÃO EDUCACIONAL DE MARIANA 
FAMA - FACULDADE DE ADMINISTRAÇÃO DE MARIANA 
3ª vez: 
N – 1 Comparações 
Truca := false 
Vetor já ORDENAO! 
FEMAR - FUNDAÇÃO EDUCACIONAL DE MARIANA 
FAMA - FACULDADE DE ADMINISTRAÇÃO DE MARIANA 
Bubble Sort melhorado 
troca:=true; 
 for vez:=1 to NUM do // número de vezes 
 begin 
 if troca = false // melhoria - a 1ª vez que não ocorrer trocas, o loop termina. 
 then break; 
 troca:= false; 
 for j:=1 to NUM-1 do 
 if(VET[j]>VET[j+1]) then // comparações por vez. 
 begin 
 AUX:=VET[j]; 
 VET[j]:=VET[J+1]; 
 VET[j+1]:=AUX; 
 troca:=true; // melhoria 
 end; 
 end; 
FEMAR - FUNDAÇÃO EDUCACIONAL DE MARIANA 
FAMA - FACULDADE DE ADMINISTRAÇÃO DE MARIANA 
1) Simule, o seu caderno, a ordenação do vetor abaixo, utilize o
método Bubble Sort melhorado:
2) Fazer um programa, em Pascal, que leia 10 números inteiros para
um vetor. Logo após, o programa deverá chamar a função 
Bubblesortmelhorado, que deverá ordenar e imprimir o vetor 
ordenado. No programa principal, imprimir a mensagem vetor 
ordenado com sucesso e o número de comparações realizadas. 
FEMAR - FUNDAÇÃO EDUCACIONAL DE MARIANA 
FAMA - FACULDADE DE ADMINISTRAÇÃO DE MARIANA 
3) Fazer um programa, em Pascal, que leia 10 nomes para um vetor. Logo
após, o programa deverá: 
1- Permitir a escolha do método de ordenação (1-Bubblesort ou 
2-Bubblesortmelhorado); 
2- retornar o número de comparações realizadas por cada um dos métodos de 
ordenação; 
3- Solicitar um nome (chave) a ser buscado; 
4- Permitir a escolha do método de busca (1-sequencial ou 2-Binária) 
5- Retornar em qual posição a chave foi encontrada ou se não foi encontrada; 
6- Retornar o número de comparações realizadas por cada um dos métodos 
de busca.