ATP-Aula05-AplicaçõesDeVetores(Ordenação)

Prévia do material em texto

Algoritmos e Técnicas de 
Programação
Aula 05: Estruturas de Dados Seqüenciais
(Aplicações de Vetores – Ordenação)
Plano de Aula
� Ordenação – Introdução
� Ordenação pelo Método da Bolha (BubbleSort)
� Ordenação pelo Método da Seleção
Introdução
� Ordenar corresponde ao processo de organizar um 
conjunto de objetos segundo uma dada ordem.
� Exemplo1: Um conjunto de pessoas pode ser organizado 
por nomes, datas de nascimento, CPFs etc.
� O objetivo da ordenação é facilitar a localização dos 
objetos:
� Exemplo: organizar um conjunto de livros para permitir 
consultas aos seus conteúdos.
� Contra-exemplo: faz pouco sentido organizar o mesmo 
conjunto de livros para reciclar suas folhas.
� Mais exemplos: lista telefônica, dicionários, índices 
remissivos de livros, lista de matriculados etc.
Introdução
� O processo de ordenação envolve executar “muitas”
vezes duas operações:
� Comparação: indica se dois elementos estão em ordem
� Troca: permuta dois elementos, o que requer três
Movimentos (atribuições) na memória.
� A eficiência de uma algoritmo de ordenação é medida 
através do número de comparações e de movimentos
(atribuições) de elementos que ele realiza, conforme o 
número o número de elementos, N.
Introdução
� Conforme a eficiência, os algoritmos de ordenação 
de vetores são classificados em:
� Algoritmos diretos: são simples, fáceis de entender e 
programar, mas devem usados em conjuntos “pequenos”:
� Bolha
� Seleção direta
� Inserção direta
� Métodos eficientes: têm detalhes mais complexos, são 
mais difíceis de entender e programar, porém são muito 
eficientes para valores de N “grandes”:
� QuickSort, HeapSort, Heapsort
� (Aguardem a Disciplina Estruturas de Dados I)
Método da Bolha
� Dado um vetor V contendo N elementos, o método 
trabalha assim:
� Na primeira “rodada”, faz N-1 comparações entre 
elementos adjacentes (Vi e Vi+1), trocando-os de 
ordem sempre que Vi > Vi+1. Isso fará com que o 
maior elemento fique na última posição, portanto no 
seu local correto.
� Na segunda rodada, faz o mesmo, porém agora 
sobre os N-1 elementos restantes. Ao final, o maior 
elemento deste conjunto ficará na penúltima 
posição.
Método da Bolha
� Na rodada N-1, restam apenas dois elementos não 
ordenados e basta uma comparação (e uma troca, se 
necessário) para colocá-los em ordem.
� O método tem esse nome porque se consideramos o 
vetor na vertical (de baixo para cima) e cada elemento 
como uma bolha de diâmetro proporcional ao seu valor, 
teríamos as bolhas maiores subindo.
40
36
28
40
36
28 40
36
28
40
36
281
2
3
Algoritmo – Método da Bolha
//A = A[1], A[2],..., A[n]
procedimento MetodoBolha(PorRef A : Vetor; n : inteiro)
declare
i, j : inteiro
inicio
para i ← n até↓ 2 faça
para j ← 1 até i-1 faça
se A[j] > A[j+1] então
Troca(A[i], A[j])
fimse
fimpara
fimpara
fim
Ordenação por Seleção
� Também é muito simples e faz significativamente
menos trocas que o método da bolha.
� Princípio para ordenar A com N elementos:
� Dentre os N elementos, seleciona o de menor valor e 
troca-o com aquele da 1ª posição.
� Dentre os N-1 restantes, selecione o de menor valor e 
troque-o com aquele na 2ª posição.
� Repita a operação até que só reste um elemento não 
ordenado, o qual será o maior valor e já estará na 
última posição
Algoritmo – Método da Seleção
//A = A[1], A[2],..., A[n]
procedimento MetodoSeleção(PorRef A: Vetor; n: inteiro)
declare
i, j, Min : inteiro
inicio
para i ← 1 até n-1 faça
Min ← i
para j ← i+1 até n faça
se A[j] < A[Min] então
Min ← j
fimse
fimpara
Troca(A[Min], A[i]) //Coloca o mínimo na sua posição
fimpara
fim
Exercício 1
� Implementar em C o algoritmo de ordenação 
por Seleção
Solução 1:
void MetodoSelecao(int v[], int n){
int i, j, Min;
for (i=0; i < n-1; i++){
Min = i;
for (j=i+1; j < n; j++)
if (v[j] < v[Min])
Min = j;
TrocaElementos(v, n, Min, i);
}
}
Exercício 2
� Um determinada aplicação requer o 
processamento dos 10 menores valores 
inteiros de um conjunto que contém bem 
mais que 10 valores. Modifique o método da 
seleção para que ele selecione os 10 
menores valores, sem ordenar todo o 
conjunto.
Solução 2:
void DezMaiores(int v[], int n){
int i, j, Min;
for (i=0; i < 10; i++){
Min = i;
for (j=i+1; j < n; j++)
if (v[j] < v[Min])
Min = j; 
TrocaElementos(v, n, Min, i);
}
}
Exercício 3
� Implemente uma função em C que funda 2 
vetores de inteiros ordenados a e b, 
contendo na e nb elementos, em um vetor c, 
o qual também deverá estar ordenado. 
Admita que c tenha capacidade (na+nb) 
sufuciente!
� Exemplo: 
� a = [12, 25, 48, 54]
� b = [17, 22, 25, 31]
� c = a + b = [12, 17, 22, 25, 25, 31, 48, 54]
Solução 3
//funde os vetores ordenados "a" e "b" em "c", 
//de modo que "c" também seja ordenado
void funde(int a[], int na, int b[], int nb, int c[], int * nc)
{
int i = 0, j = 0, k = 0;
while (i < na && j < nb)
{ if (a[i] <= b[j])
c[k++] = a[i++];
else
c[k++] = b[j++];
}
while (i < na)
c[k++] = a[i++];
while (j < nb)
c[k++] = b[j++];
*nc = k;
}