Método da Bolha - Lógica - Pseudo e Código

Prévia do material em texto

Estruturas de Dados CCT0021 – Método da Bolha Página 1 de 12 
Pseudocódigo e Codificação em C++ 
Método da Bolha (classificação de vetor) 
 
Lógica e pseudocódigo da classificação de um vetor (ou matriz de uma 
dimensão) de, por exemplo, seis elementos, utilizando o método da bolha. 
 
 
 
 
A idéia é comparar os elementos dois a dois e ir “jogando” os elementos mais 
altos para as últimas posições do vetor até obter o vetor classificado. 
 
 
 
Uma vez que o elemento mais alto tenha atingido a mais alta posição, o 
tamanho do vetor, a ser classificado é reduzido, de uma unidade até que o 
tamanho seja maior ou igual a dois. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
5 4 3 2 6 155 44 33 22 66 11
 
1 2 3 4 5 611 22 33 44 55 66
 
Estruturas de Dados CCT0021 – Método da Bolha Página 2 de 12 
Pseudocódigo e Codificação em C++ 
 
 
 
Primeiro passo 
 
 
 
 
5 4 3 2 6 1
4 5 3 2 6 1
4 3 5 2 6 1
4 3 2 5 6 1
4 3 2 5 6 1
4 3 2 5 1 6
5 4 3 2 6 155 44 33 22 66 11
4 5 3 2 6 144 55 33 22 66 11
4 3 5 2 6 144 33 55 22 66 11
4 3 2 5 6 144 33 22 55 66 11
4 3 2 5 6 144 33 22 55 66 11
4 3 2 5 1 644 33 22 55 11 66
 
Estruturas de Dados CCT0021 – Método da Bolha Página 3 de 12 
Pseudocódigo e Codificação em C++ 
 
Observe que o elemento 6 já se encontra na última posição do vetor. Assim, 
vamos reduzir de uma unidade o tamanho, que passa a ser 5, que ainda é 
maior ou igual a 2. A nova configuração, levando-se em conta as comparações 
do passo anterior, é a seguinte: 
 
 
 
Observe que o elemento 5 já se encontra na última posição do novo tamanho 
do vetor. Assim, vamos reduzir de uma unidade o tamanho, que passa a ser 4, 
4 3 2 5 1
3 4 2 5 1
3 2 4 5 1
3 2 4 5 1
3 2 4 1 5
4 3 2 5 144 33 22 55 11
3 4 2 5 133 44 22 55 11
3 2 4 5 133 22 44 55 11
3 2 4 5 133 22 44 55 11
3 2 4 1 533 22 44 11 55
 
Estruturas de Dados CCT0021 – Método da Bolha Página 4 de 12 
Pseudocódigo e Codificação em C++ 
que ainda é maior ou igual a 2. A nova configuração, levando-se em conta as 
comparações do passo anterior, é a seguinte: 
 
 
 
Observe que o elemento 4 já se encontra na última posição do novo tamanho 
do vetor. Assim, vamos reduzir de uma unidade o tamanho, que passa a ser 3, 
3 2 14
3 2 14
3 2 14
3 2 41
3 2 1433 22 1144
3 2 1433 22 1144
3 2 1433 22 1144
3 2 4133 22 4411
 
 
Estruturas de Dados CCT0021 – Método da Bolha Página 5 de 12 
Pseudocódigo e Codificação em C++ 
que ainda é maior ou igual a 2. A nova configuração, levando-se em conta as 
comparações do passo anterior, é a seguinte: 
 
 
 
Observe que o elemento 3 já se encontra na última posição do novo tamanho 
do vetor. Assim, vamos reduzir de uma unidade o tamanho, que passa a ser 2, 
que agora é igual a 2. A nova configuração, levando-se em conta as 
comparações do passo anterior, é a seguinte: 
 
 
3 2 1
2 3 1
2 1 3
3 2 133 22 11
2 3 122 33 11
2 1 322 11 33
 
Estruturas de Dados CCT0021 – Método da Bolha Página 6 de 12 
Pseudocódigo e Codificação em C++ 
 
 
Observe que o elemento 2 já se encontra na última posição do novo tamanho 
do vetor. Assim, vamos reduzir de uma unidade o tamanho, que passa a ser 1, 
que agora é menor que 2. Portanto, não se justifica fazer mais comparações, 
porque o menor elemento 1, já se encontra na primeira posição. 
 
 
 
 
 
 
 
 
 
2 1
1 2
2 122 11
1 211 22
 
Estruturas de Dados CCT0021 – Método da Bolha Página 7 de 12 
Pseudocódigo e Codificação em C++ 
Pseudocódigo do método da bolha 
 
 
INICIO 
 
 inteiro vet[6]; 
 
 inteiro aux, //auxiliar para troca de elementos 
 bolha, //indicador de mais alto elemento fora de ordem 
 lsup, //indicador do tamanho do vetor a ser pesquisado, sendo 
 //o valor inicial igual a 6 
 i; //indicador (posição) do elemento do vetor 
 
 carregar vet 
 
 lsup � 6; 
 
 enquanto lsup > 1 faça 
 
 bolha � 0; 
 
 para i de 0 até lsup – 1 faça //considera posição iniciado com 0 
 
 se vet [ i ] > vet [ i + 1 ] 
 
 então //troca elemento com i + 1 
 
 aux � vet [ i ]; 
 vet [ i ] � vet [ i + 1 ]; 
 vet [ i + 1 ] � aux; 
 bolha �i; 
 fim se 
 fim para 
 
 lsup � bolha; //aponta para a última posição de troca 
 
 fim enquanto 
 
 mostrar vet; 
 
FIM 
 
 
 
 
 
 
 
 
 
Estruturas de Dados CCT0021 – Método da Bolha Página 8 de 12 
Pseudocódigo e Codificação em C++ 
Codificação do Pseudocódigo do método da bolha em C++: 
 
#include <cstdlib> 
#include <iostream> 
 
using namespace std; 
 
const int TAMANHO = 6; 
int main(int argc, char *argv[]) 
{ 
 int vet[] = {5, 2, 1, 3, 4, 6}; 
 int aux, lsup, bolha; 
 
 lsup = 6; 
 while ( lsup > 0 ) 
 { 
 bolha = 0; 
 for (int i = 0; i < lsup - 1 ; i++) 
 { 
 if(vet[i] > vet[i + 1]) 
 { 
 aux = vet[i]; 
 vet[i] = vet[i + 1]; 
 vet[i + 1] = aux; 
 bolha = i + 1; 
 } 
 } 
 lsup = bolha; 
 } 
 for (int i = 0; i < TAMANHO; i++) 
 printf("\n%d",vet[i]); 
 
 cout << '\n' << endl; 
 
 system("PAUSE"); 
 return EXIT_SUCCESS; 
} 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Estruturas de Dados CCT0021 – Método da Bolha Página 9 de 12 
Pseudocódigo e Codificação em C++ 
PESQUISA BINÁRIA 
 
 
Dado um vetor X de Y elementos, por exemplo, verificar se existe um elemento 
igual a K (chave de pesquisa) no vetor. Se existir, imprimir a chave e posição 
onde foi encontrada a chave; se não, imprimir: “chave k não encontrada”. O 
vetor X tem que estar ordenado e a chave K tem que ser lida. 
 
Neste método, para pesquisar um elemento será utilizada a pesquisa binária, 
desde que o vetor já esteja ordenado. Nesta pesquisa procuramos o elemento 
K dividindo o vetor em duas partes (por isso bi, de duas partes) e testando em 
qual das duas a chave deveria estar. Procedendo da mesma forma para a 
parte provável, e assim sucessivamente: 
 
 
Neste exemplo, pode-se visualizar que o vetor tem 11 elementos. Para saber 
posição meio do vetor, fez-se a divisão do tamanho(11) por 2. Então compara-
se o vetor[ meio ] com a chave, para saber em que parte a chave deve estar. 
Procede-se da mesma forma para as outras partes, até encontra ou não a 
chave. 
 
K
X
K
K
K
X
KK
K
 
Estruturas de Dados CCT0021 – Método da Bolha Página 10 de 12 
Pseudocódigo e Codificação em C++ 
 
 
 
Pseudocódigo da pesquisa binária 
 
INICIO 
 
 inteiro vet[11];//pelo exemplo, uma vez que tem que ser maior que 3 
 
 inteiro comeco, //indicador do primeiro elemento da parte do vetor 
 //a considerar. 
 fim, //indicador do último elemento da parte do vetor 
 //a considerar. 
 meio, //indicador elemento do meio da parte do vetor considerada 
 k; //elemento procurado 
 
 carregar vet 
 
 ler k; 
 
 começo � 0; //considere a primeira posição começando com zero 
 fim � 10; //última posiçãodo vetor 
 
 repita 
 
 meio � (comeco + fim)/2; 
 
 se k < vet [ meio ] 
 
 então 
 fim � meio – 1; 
 
 senão comeco � meio + 1; 
 
 fim se 
 
 até ((vet [ meio ] = k) ou (comeco > fim)) 
 
 se vet [ meio ] != k 
 então imprima (“NÃO EXISTE O ELEMENTO”); 
 senão imprima (“A CHAVE “, k, “ ESTÁ NA POSIÇÃO: “, meio) ; 
 
 fim se; 
 
FIM 
 
 
Estruturas de Dados CCT0021 – Método da Bolha Página 11 de 12 
Pseudocódigo e Codificação em C++ 
Exercício: Considere o segmento de programa a seguir: 
 
 
#include <stdio.h> 
#include <stdlib.h> 
 
int main(int argc, char *argv[]) 
{ 
 int vetor[ ] = {1,2,3,4,5,6,7}; 
 
 system("PAUSE"); 
 return 0; 
} 
 
 Como se percebe no segmento de programa acima, o mesmo está 
incompleto e possui um array já iniciado e ordenado em ordem crescente. 
Complete-o (1) para pesquisar se existe um certo elemento igual a k (chave) 
no array e (2) para imprimir uma das mensagens: “A chave de pesquisa 
k esta na posição x do vetor.” (a posição x onde foi encontrada a 
chave é a mesma que o elemento ocupa no array) ou, então, “Não existe 
o elemento K no vetor.”. A chave deve ser lida de maneira interativa. 
 
 É obrigatório utilizar o método da pesquisa binária, visto em sala de aula, 
para a pesquisa solicitada. 
 
Exemplo de um lay-out de entrada e saída 
 
Entre com o valor(inteiro) da chave a ser pesquisada no vetor: 3 
 
A chave de pesquisa 3 esta na posicao 2 do vetor. 
 
Pressione qualquer tecla para continuar. . . 
 
 
Entre com o valor(inteiro) da chave a ser pesquisada no vetor: 9 
 
Nao existe o elemento 9 no vetor. 
 
Pressione qualquer tecla para continuar. . . 
 
 
#include <stdio.h> 
#include <cstdlib> 
#include <iostream> 
#include <ctype.h> 
#include <conio.h> 
 
using namespace std; 
 
int main(int argc, char *argv[]) 
{ 
 
 int vet[] = {1,2,3,4,5,6,7}; 
 int chave; 
 
 int inicio, meio, fim; 
 
Estruturas de Dados CCT0021 – Método da Bolha Página 12 de 12 
Pseudocódigo e Codificação em C++ 
 inicio = 1; 
 fim = 7; 
 
 cout << "\nEntre com o valor(inteiro) da chave a ser pesquisada no 
vetor: "; 
 cin >> chave; 
 
 do 
 { 
 meio = (inicio + fim)/2; 
 if (chave < vet[meio]) 
 fim = meio - 1; 
 else inicio = meio + 1; 
 }while((vet[meio] != chave) &&(inicio <= fim)); 
 
 if (vet[meio] != chave) 
 cout << "\nNao existe o elemento " << chave << " no vetor." << 
"\n\n"; 
 else 
 cout << "\nA chave de pesquisa " << chave << " esta na posicao " 
 << meio << " do vetor." << "\n\n"; 
 
 system("PAUSE"); 
 return 0; 
} 
 
 
Entre com o valor(inteiro) da chave a ser pesquisada no vetor: 3 
 
A chave de pesquisa 3 esta na posicao 2 do vetor. 
 
Pressione qualquer tecla para continuar. . . 
 
 
 
Entre com o valor(inteiro) da chave a ser pesquisada no vetor: 9 
 
Nao existe o elemento 9 no vetor. 
 
Pressione qualquer tecla para continuar. . .