Algoritmos
Escher
Agenda
• Método de Ordenação;
• Método de Pesquisa;
• Exercícios.
Conceitos Iniciais
Métodos de Ordenação – Bolha:
 O algoritmo de “ordenação bolha”, ou “bubble sort”,
recebeu este nome pela forma usada para descrevê-lo: os
elementos maiores são mais leves, e sobem como bolhas
até suas posições corretas.
 Simples, fácil de entender e implementar;
 Um dos mais conhecidos métodos de ordenação;
 Baixa eficiência;
 Utilizado basicamente para desenvolvimento do
raciocínio ou onde não exige-se muita performance;
Conceitos Iniciais
Métodos de Ordenação – Bolha:
 Critério de ordenação: ordem crescente ou decrescente.
 A filosofia básica deste método consiste em:
1. “Varrer” o vetor, comparando os elementos
vizinhos entre si: se (V[I] > V[I+1]).
2. Caso estejam fora de ordem, os mesmos trocam
de posição entre si.
Conceitos Iniciais
Métodos de Ordenação - Bolha:
 A filosofia básica - continuação:
3.
Procede-se assim até o final do vetor. Na primeira
“varredura” verifica-se que o último elemento do vetor já
está no seu devido lugar (no caso de ordenação
crescente, ele é o maior de todos).A segunda “varredura”
é análoga à primeira e vai até o penúltimo elemento.
4.
Este processo é repetido até que seja feito um número de
varreduras igual ao número de elementos a serem
ordenados menos um. Ao final do processo o vetor está
classificado segundo o critério escolhido.
Método da BOLHA (ordem crescente)
Método da BOLHA (ordem crescente)
prog metodobolha
int L, c , AUX, V[5], n;
# onde L, c: são variáveis de controle
# AUX: variável auxiliar para troca
# V[5] : tabela ou vetor a ser ordenado
n <- 5; # tamanho do vetor
imprima " \nInforme os dados da tabela: \n";
para (L <- 0; L < n; L++) {
imprima “Digite valor: ";
leia V[L];
}
imprima "\nValores Informados: ";
para (L <- 0; L < n; L++)
{
imprima V[L] , " ";
}
Método da BOLHA (ordem crescente)
para (L<- n-1; L>=1; L--) {
para (c<- 0; c<L; c++) {
se (V[c]>V[c+1]) { /* troca */
AUX <- V[c];
V[c] <- V[c+1];
V[c+1] <- AUX;
}
}
}
imprima "\nValores Ordenados:";
para (L <- 0; L < n; L++)
{
imprima V[L], " ";
}
fimprog
Ordenação
Conceitos Iniciais
Métodos de Ordenação – Seleção (Livro):
 Critério de ordenação: ordem crescente ou decrescente.
 A idéia básica do Método de Seleção é, a cada passagem
pelo vetor, selecionar o menor elemento e colocar este
elemento o mais a esquerda possível.
 A cada passo encontra-se o menor elemento dentro do segmento
com os elementos não selecionados;
 Troca-se este elemento com o primeiro elemento do segmento;
 Atualiza-se o tamanho do segmento (menos um elemento);
 Este processo é repetido até que o segmento fique com apenas
um elemento.
Método da SELEÇÃO
Método da SELEÇÃO
prog metodoselecao
int L, c , AUX, V[5], n;
# onde L, c: são variáveis de controle
# AUX: variável auxiliar para troca
# V[5] : tabela ou vetor a ser ordenado
n <- 5; # tamanho do vetor
imprima " \nInforme os dados da tabela: \n";
para (L <- 0; L < n; L++) {
imprima “Digite valor: ";
leia V[L];
}
imprima "\nValores Informados: ";
para (L <- 0; L < n; L++)
{
imprima V[L] , " ";
}
Método da SELEÇÃO
para (L<-0; L<n-1; L++) {
para (c<-(L+1); c<=n-1; c++) {
se(V[L] > V[c])
{
AUX <- V[L];
V[L] <- V[c];
V[c] <- AUX;
}
}
}
imprima "\nValores Ordenados:";
para (L <- 0; L < 5; L++)
{
imprima V[L], " ";
}
fimprog
Ordenação
Conceitos Iniciais
Métodos de Pesquisa:
 PESQUISA: O problema de procurar (pesquisar) alguma
informação numa tabela ou num catálogo é muito
comum.
 Exemplo:
• procurar o telefone de uma pessoa no catálogo
• procurar o nº da conta de um certo cliente
• consultar um determinado saldo em um terminal
automático
Conceitos Iniciais
Métodos de Pesquisa:
 A tarefa de “pesquisa”, “procura” ou “busca” é, como se
pode imaginar, uma função muito utilizada.
 As rotinas que executam a busca devem ser eficientes
(menor tempo possível).
 EFICIÊNCIA
 O TEMPO GASTO pesquisando dados em tabelas
depende do TAMANHO da tabela e do
ALGORITMO utilizado na busca.
Conceitos Iniciais
Métodos de Pesquisa:
 Método da Pesquisa Sequêncial
 Método da Pesquisa Binária
Conceitos Iniciais
Métodos de Pesquisa - SEQUÊNCIAL:
 A pesquisa seqüencial ou linear é o método mais
objetivo para se encontrar um elemento particular em
um conjunto não classificado.
 A idéia básica da Pesquisa Sequêncial é localizar o
elemento procurado através de comparações sucessivas
e sequênciais, a partir do primeiro elemento do vetor.
Conceitos Iniciais
Métodos de Pesquisa - SEQUÊNCIAL:
 A pesquisa termina quando o elemento é encontrado ou
quando é atingido o fim do vetor.
 No melhor caso, acha-se o elemento procurado na 1a
comparação, no pior na Na comparação. Na média, o
número de comparações é N/2
Conceitos Iniciais
Métodos de Pesquisa - SEQUÊNCIAL:
 Comparar o elemento procurado (DADO) com cada um
dos elementos da tabela TAB na seqüência em que
aparecem na tabela.
Tabela (TAB)
3 6 1 2 0
2
2
2 2
Procurado (DADO) 2
POS  3
Conceitos Iniciais
Métodos de Pesquisa - SEQUÊNCIAL:
 Para os métodos de pesquisa que se seguem vamos
denotar por:
TAB - um vetor contendo N elementos inteiros
distintos.
DADO - elemento a ser procurado em TAB
ACHOU - indica o sucesso ou falha na pesquisa.
POS - aponta para a posição do elemento encontrado.
Pesquisa Seqüêncial
prog BUSCASEQUENCIAL
int
i /*variável de controle*/,
N /*tamanho da tabela*/,
DADO /*elemento a ser procurado na tabela*/,
POS /*posição em que se encontra o elemento*/,
TAB [5] /*tabela para os valores*/,
ACHOU; /*valor lógico que representa o sucesso da busca*/
imprima "\nInforme os dados da tabela: ";
para (i <- 0; i < 5; i++)
{
leia TAB[i];
}
imprima "\nValores Informados:";
para (i <- 0; i < 5; i++)
{
imprima TAB[i] , " ";
}
Pesquisa Seqüêncial
imprima "\nDigite o elemento a ser procurado: ";
leia DADO;
INEFICIENTE: O processo de busca continua mesmo
ACHOU <- 0;
depois que o elemento foi encontrado.
para (i <- 0; i < 5; i++) {
se (TAB[i] == DADO) {
ACHOU <- 1;
POS <- i;
}
Solução: Parar a
}
busca quando o DADO
for encontrado.
se (ACHOU == 1)
{
imprima DADO, " se encontra na posicao ", POS;
}
senao
{
imprima DADO, " NAO se encontra na TABELA.";
}
fimprog
Pesquisa Seqüêncial – solução 02
imprima "\nDigite o elemento a ser procurado: ";
leia DADO;
//*****
ACHOU <- 0;
EFICIENTE: O processo de busca pára quando o
elemento é encontrado.
i = 0;
enquanto ((ACHOU == 0) && (i <= N)) {
se (TAB[i] == DADO)
ACHOU <-1;
senao
Condição melhorada,
i++;
prevê sucesso na busca e
fim da tabela.
}
se (ACHOU == 1)
imprima DADO, " se encontra na posicao “, i;
senao
imprima DADO, " NAO se encontra na TABELA.";
Programa
fimprog
Conceitos Iniciais
Métodos de Pesquisa - Binária:
 A idéia básica da Pesquisa Binária consiste em diminuir
cada vez mais o intervalo de busca.
 Neste método, a tabela a ser pesquisada deve estar
previamente ordenada (classificada).
 Encontra-se, inicialmente, o elemento central da tabela
dividindo-a, assim, em duas metades.
 Verifica-se em que metade o elemento procurado se
encontra e abandona-se a outra metade.
Conceitos Iniciais
Métodos de Pesquisa - Binária:
 Conforme o resultado da operação efetuada, toma-se
como novo intervalo de pesquisa uma das metades do
intervalo anterior e o processo de busca é repetido.
 O término do processo se dá quando o elemento
desejado é localizado ou quando o intervalo de busca
torna-se vazio (significando que o elemento desejado
não está presente na tabela).
Conceitos Iniciais
Métodos de Pesquisa - Binária:
 A cada passo divide-se a área de pesquisa à metade;
 Caso a tabela tenha 1500 valores:
1500/2  750
750/2  375,5
376/2  188
188/2  94
94/2  47
47/2  23,5
24/2  12
12/2  6
6/2  3
3/2  1,5
2/2  1
O número máximo de
passos é log2 N,
arredondado ao inteiro
mais próximo. Se N =
12. Temos 12 = 24 =>
log2 24 = 4 (máx.)
4
7
8
inicio
meio
fim
0
5
11
Elem = 22
10 14 21 22 36 62 77 81 91
22 >21, inicio = meio +1
4
7
8
inicio
meio
fim
6
8
11
10 14 21 22 36 62 77 81 91
22 < 62, fim= meio -1
4
7
8
inicio
meio
fim
6
6
7
10 14 21 22 36 62 77 81 91
22 = 22, o elem está na posição meio
Pesquisa Binária
prog metodobinario
//Declarações
int i /*variável de controle*/, N /*tamanho da tabela*/,
DADO /*elemento a ser procurado na tabela*/,
MEIO /*posição central tabela*/,
INIC /*posição inicial da busca*/,
FIM /*posição final da busca */,
TAB [30] /*tabela para os elementos */,
ACHOU; /*valor lógico que representa o sucesso da busca*/
imprima "Digite o tamanho da tabela: ";
leia N;
imprima "\nInforme os dados da tabela: ";
para (i <- 0; i < N; i++)
leia TAB[i];
imprima "\nValores Informados:";
para (i <- 0; i < N; i++)
imprima TAB[i], " ";
Pesquisa Binária
imprima"\nDigite o elemento a ser procurado: ";
leia DADO;
//*****
Inicialização do intervalo de busca
ACHOU <- 0;
INIC <- 0;
FIM <- (N - 1);
enquanto ((INIC <= FIM) && (ACHOU == 0)) {
Determinação da posição central
MEIO <- (INIC + FIM) / 2;
//divisao de inteiro, resulta inteiro
se (TAB[MEIO] == DADO)
ACHOU <- 1;
// o elemento foi encontrado
senao {
se (TAB[MEIO] > DADO)
FIM <- (MEIO - 1); // ajusta fim do vetor
senao
INIC <- (MEIO + 1); // ajusta inicio do vetor
}
}
se (ACHOU == 1)
Mudança do intervalo de busca
imprima DADO , " foi encontrado. ";
senao
imprima DADO, " NAO se encontra na TABELA.";
Programa
fimprog
Referências
 Lopes, A. & Garcia, G. – Introdução a Programação.
 Schildt – C Completo e Total.
Obrigado
E Agora???
Exercícios!!!
Exercícios Propostos
1.
2.
Faça um programa para ler dois vetores e intercalar estes dois vetores
formando o vetor . Apresentar o vetor C gerado, ordenar este vetor C e
mostrá-lo também.
Verifique se os elementos de um vetor A estão em ordem crescente.
FIM