Aula 05 parte8 1

Prévia do material em texto

Programação em C 
(Parte 8 – Ordenação e Busca)
Prof. Valério Rosset
Profa. Mariá C. V. Nascimento 
Rosset 
Slides adaptados do material da Profa. Rosely Sanches e 
Simone Senger de Souza, ICMC.
 
Ordenação
 ORDENAÇÃO é uma das tarefas básicas 
em processamento de dados
 A ordenação de um vetor significa 
classificar os seus elementos
 Colocar os elementos do vetor em ordem de 
acordo com algum critério
 
 Supor que os elementos de um vetor 
sejam inteiros
 Critério de ordenação: 
 ordem crescente
 ordem decrescente
Ordenação de Vetores
 
 Existem vários algoritmos de ordenação
 Diferenciam pela velocidade da ordenação (e 
complexidade de implementação)
 Métodos de ordenação: (simples)
 Método da Seleção
 Método da Bolha
Algoritmos de Ordenação
 
Método da Seleção
 Funcionamento:
 a cada passagem pelo vetor, selecionar o 
menor elemento e colocar este elemento o 
mais a esquerda possível no vetor.
 Para isto deve-se trocar as posições dos 
elementos do vetor
 Na primeira passagem troca-se o menor elemento 
com o que está na primeira posição
 Na segunda passagem troca-se o segundo menor 
elemento com o que está na segunda posição
 Assim por diante
 
Método da Seleção
 Desse modo, na passagem i só se deve 
procurar o menor elemento a partir do i-
ésimo até o N-ésimo elemento do vetor 
(os elementos anteriores já estarão 
ordenados). 
 Note-se que serão necessárias (N-1) 
passagens, pois, na última passagem, o N-
ésimo elemento 
já estará na sua posição correta
 
Método da Seleção 
(ordem crescente)
VET = [ 46 15 91 59 62 76 10 93 ]
VET = [ 46 15 91 59 62 76 10 93 ]
VET = [ 10 15 91 59 62 76 45 93 ]
VET = [ 10 15 91 59 62 76 45 93 ]
E assim por diante …. até o vetor estar ordenado
 
Algoritmo do Método da Seleção
Funcao_Ordena_Selecao(inteiro vetor[], inteiro tam)
Inicio
inteiro i, j, min, aux;
para i de 0 até tam-2 faça
min = i;
para j de i+1 até tam faça
 se (vetor[j] < vetor[min])
min = j;
 fim-se;
fim-para;
aux=vetor[i]; 
vetor[i]=vetor[min]; 
vetor[min]=aux; 
fim-para;
Fim.
O vetor é passado 
como parâmetro – por 
referência
Percorre todo o vetor 
até o elemento n-1 
Percorre do elemento 
i+1 até o último.
Armazena a posição 
(índice) do menor 
elemento
Troca os elementos, 
colocando-os na ordem 
crescenteA variável I controla o pivô
A variável J controla os elementos a frente do pivô
 
Método da Seleção 
(ordem crescente)
VET = [ 46 15 91 59 62 76 10 93 ]
VET = [ 10 15 91 59 62 76 46 93 ]
VET = [ 46 15 91 59 62 76 10 93 ]
VET = [ 10 15 91 59 62 76 45 93 ]
min=0
i=0
min=6
i=0
min=1
i=1
min=1
i=1
 
Método da Seleção 
(ordem crescente)
VET = [ 10 15 91 59 62 76 45 93 ]
VET = [ 10 15 45 59 62 76 91 93 ]
VET = [ 10 15 45 59 62 76 91 93 ]
VET = [ 10 15 45 59 62 76 91 93 ]
min=6
i=2
VET = [ 10 15 91 59 62 76 45 93 ]min=2i=2
min=3
i=3
min=3
i=3
min=4
i=4
 
Método da Seleção 
(ordem crescente)
VET = [ 10 15 45 59 62 76 91 93 ]
VET = [ 10 15 45 59 62 76 91 93 ]
VET = [ 10 15 45 59 62 76 91 93 ]
VET = [ 10 15 45 59 62 76 91 93 ]
VET = [ 10 15 45 59 62 76 91 93 ]
VET = [ 10 15 45 59 62 76 91 93 ]
Vetor Final
min=4
i=4
min=5
i=5
min=5
i=5
min=6
i=6
min=6
i=6
 
Exercício de Fixação
 Utilizando o algoritmo anterior (método 
da seleção), faça a ordenação do 
seguinte vetor:
 Vetor = { 4, 8, 2, 3, 7}
 
Método da Bolha
 É mais popular que o método da seleção, 
embora seu desempenho seja inferior
 Funcionamento:
 A cada passagem pelo vetor, o elemento da 
i-ésima posição é selecionado e transferido 
para a sua posição adequada.
 
Algoritmo do Método da Bolha
Funcao_Ordena_Bolha(inteiro vetor[], inteiro tam)
Inicio
inteiro i, j, aux;
para i de 0 até tam-1 faça
para j de tam-1 até i+1 passo –1 faça
 se (vetor[j-1] > vetor[j]
aux=vetor[j-1]; 
vetor[j-1]=vetor[j]; 
vetor[j]=aux;
 fim-se;
fim-para;
fim-para;
Fim.
 
VETOR DESORDENADOVETOR DESORDENADO
[ 15 46 91 59 62 76 10 93 ]
[ 15 46 91 59 62 76 10 93 ]
[ 15 46 91 59 62 10 76 93 ]
[ 15 46 91 59 10 62 76 93 ]
[ 15 46 91 10 59 62 76 93 ]
[ 15 46 10 91 59 62 76 93 ]
[ 15 10 46 91 59 62 76 93 ]
[ 10 15 46 91 59 62 76 93 ]
[ 10 15 46 91 59 62 76 93 ]
[ 10 15 46 59 91 62 76 93 ]
[ 10 15 46 59 62 91 76 93 ]
[ 10 15 46 59 62 76 91 93 ]
VETOR ORDENADOVETOR ORDENADO
[ 10 15 46 59 62 76 91 93 ]
i=0; j= 7
i=0; j= 6
i=0; j= 5
i=0; j= 4
i=0; j= 3
i=0; j= 2
i=0; j= 1
i=1; j= 7
i=1; j= 4 ...
i=2; j= 5 ...
i=3; j= 6 ...
 
VETOR DESORDENADOVETOR DESORDENADO
[ 15 46 91 59 62 76 10 93 ]
[ 15 46 91 59 62 76 10 93 ]
[ 15 46 91 59 62 10 76 93 ]
[ 15 46 91 59 10 62 76 93 ]
[ 15 46 91 10 59 62 76 93 ]
[ 15 46 10 91 59 62 76 93 ]
[ 15 10 46 91 59 62 76 93 ]
[ 10 15 46 91 59 62 76 93 ]
[ 10 15 46 91 59 62 76 93 ]
[ 10 15 46 59 91 62 76 93 ]
[ 10 15 46 59 62 91 76 93 ]
[ 10 15 46 59 62 76 91 93 ]
VETOR ORDENADOVETOR ORDENADO
[ 10 15 46 59 62 76 91 93 ]
i=0; j= 7
i=0; j= 6
i=0; j= 5
i=0; j= 4
i=0; j= 3
i=0; j= 2
i=0; j= 1
i=1; j= 7
i=1; j= 4 ...
i=2; j= 5 ...
i=3; j= 6 ...
Não troca 
mais nada
 
Exercício de Fixação
 Utilizando o algoritmo anterior (método 
da bolha), faça a ordenação do seguinte 
vetor:
 Vetor = { 4, 8, 2, 3, 7}
 
Busca Sequencial e Binária
• Busca Sequencial 
– Busca Sequencial: compara-se cada valor de 
um conjunto n com o valor esperado 
sequencialmente.
3 5 56 45 7 1
0 1 2 3 4 5 
56
v
x
for (i=0;i<n;i++)
 if (x==v[i])
 printf (“encontrou!”);
 
 
Busca Sequencial e Binária
• Busca Binária 
– Busca Binária: quebra-se o problema em 
partes para encontrar a solução.
• Porém o vetor precisa estar ordenado para 
que a busca funcione.
3 5 564571
0 1 2 3 4 5 
 
Busca Binária
Algoritmo de Busca binária (vetor 
ordenado crescente):
int busca_bin (int n, int* vet, int elem)
{ /* no inicio consideramos todo o vetor */
int ini = 0;
int fim = n-1;
int meio;
/* enquanto a parte restante for maior que zero */
while (ini <= fim) {
meio = (ini + fim) / 2;
if (elem < vet[meio])
fim = meio – 1; /* ajusta posicão final */
else if (elem > vet[meio])
ini = meio + 1; /* ajusta posicão inicial */
else
return meio; /* elemento encontrado */
}/* não encontrou */
return -1; }
 
Busca Binária
Ex. Busca Binária:
n=6, elem=7
3 5 564571
0 1 2 3 4 5 
Passo 1: ini=0, fim=5, meio=2;
 
Busca Binária
Ex. Busca Binária:
n=6, elem=7
3 5 564571
0 1 2 3 4 5 
Passo 1: ini=0, fim=5, meio=2;
56457Passo 2: ini=3, fim=5, meio=4;
 
Busca Binária
Ex. Busca Binária:
n=6, elem=7
3 5 564571
0 1 2 3 4 5 
Passo 1: ini=0, fim=5, meio=2;
56457Passo 2: ini=3, fim=5, meio=4;
Passo 3: ini=3, fim=4, meio=3; 457
 
Busca Binária
Ex. Busca Binária:
n=6, elem=7
3 5 564571
0 1 2 3 4 5 
Passo 1: ini=0, fim=5,meio=2;56457Passo 2: ini=3, fim=5,meio=4;
Passo 3: ini=3, fim=4,meio=3; 457
Passo 4: return meio = 3 7
 
Exercício Prático 
1) Escreva funções de ordenação e busca 
vistas nessa aula em C. Assuma um vetor de 
entrada com tamanho N.
 
Faça um programa para testar essas funções. 
	Slide 211
	Slide 212
	Slide 213
	Slide 214
	Slide 215
	Slide 216
	Slide 217
	Slide 218
	Slide 219
	Slide 220
	Slide 221
	Slide 222
	Slide 223
	Slide 224
	Slide 225
	Slide 226
	Slide 227
	Slide 228
	Slide 229
	Slide 230
	Slide 231
	Slide 232
	Slide 233
	Slide 234
	Slide 235