Ord_Sel_Bub_01

Prévia do material em texto

Coleções
(exemplos)
A
r
r
a
y
s
 
–
O
r
d
e
n
a
ç
ã
o
Idéias Gerais
¾ sequência de valores numéricos quaisquer;
¾ Lista/conjunto de palavras num dicionário; 
Processo de organizar os dados de uma coleção/conjunto numa dada ordem
específica (crescente, decrescente, lexicográfica). Um dos problemas mais
estudados no âmbito da Ciência da Computação.
¾ Lista de clientes segundo uma dada 
chave/componente (nome, saldo médio, salário; 
gastos em compras, …);
¾ Lista telefônica (ordem alfabética de sobrenomes);
¾ Base de fichas catalográficas (biblioteca), …, etc.
(N;Z;Q;R)(N;Z;Q;R)
Algoritmo de
Ordenação
A
r
r
a
y
s
 
–
O
r
d
e
n
a
ç
ã
o
Idéias Gerais
¾ Interna:
( Dados na RAM )
¾ Externa: Outras disciplinas
ƒ Seleção;
ƒ Inserção;
ƒ BubbleSort (Bolha);
ƒ ShellSort;
ƒ MergeSort;
ƒ QuickSort;
ƒ…..
Onde: C: Conjunto/Coleção armazenados numa estrutura de array onde
existe uma relação de ordem (total, parcial) e, C’, é uma permutação de 
C.
A
r
r
a
y
s
 
–
O
r
d
e
n
a
ç
ã
o
Problema :Æ AlgoritmoOrdenação
EntradaÆÆÆ-----------Æ Saída
CÆÆÆ-----------ÆÆÆ C’
1 2 3 4{ , , , , , }nC x x x x x= "
' ' ' ' '
1 2 3 4
' '
' { , , , , , }, tal que:
, , , 1 .
n
i j
C x x x x x
x x i j i j n
=
≤ ∀ ≤ < ≤
"
Idéias Gerais
A
r
r
a
y
s
 
–
O
r
d
e
n
a
ç
ã
o
Se C = {a,b,c}, então as permutações desse conjunto são:
{a,b,c},
{a,c,b},
{b,a,c},
{b,c,a},
{c,a,b},
{c,b,a}. 
O número de permutações possíveis de um conjunto com n 
elementos é:
n!
Idéias Gerais
A
r
r
a
y
s
 
–
O
r
d
e
n
a
ç
ã
o
Se C = {1,2,3}, então as permutações desse conjunto são:
{1,2,3},
{1,3,2},
{2,1,3},
{2,3,1},
{3,1,2},
{3,2,1}. 
Idéias Gerais
Subproblemas
A
r
r
a
y
s
 
–
O
r
d
e
n
a
ç
ã
o
Método de Seleção
¾ Encontrar o menor elemento numa estrutura
de array entre as posições [lim1,lim2];
¾ Trocar dois elementos de posição numa
estrutura de array (operação de troca (swap));
Baseado na resolução sistemática dos seguintes subproblemas:
1º Passo :Æ Encontrar (selecionar) o menor elemento no array, entre 
as posições [0,Max-1] e colocá-lo na posição 0;
A
r
r
a
y
s
 
–
O
r
d
e
n
a
ç
ã
o
Método de Seleção
Após a execução desse passo:
Descrição do algoritmo:
x x x x x x x x x x x x x x x x
Subsequência não-ordenadaSubsequência ordenada
0
for (i=1;i<MAX;i++)
2º Passo :Æ Encontrar (selecionar) o menor elemento no array, entre 
as posições [1,Max-1] e colocá-lo na posição 1;
A
r
r
a
y
s
 
–
O
r
d
e
n
a
ç
ã
o
Método de Seleção
Após a execução desse passo:
Descrição do algoritmo:
x x x x x x x x x x x x x x x x
Subsequência não-ordenadaSubsequência ordenada
1
for (i=2;i<MAX;i++)
3º Passo :Æ Encontrar (selecionar) o menor elemento no array, entre 
as posições [2,Max-1] e colocá-lo na posição 2;
A
r
r
a
y
s
 
–
O
r
d
e
n
a
ç
ã
o
Método de Seleção
Após a execução desse passo:
Descrição do algoritmo:
x x x x x x x x x x x x x x x x
Subsequência não-ordenadaSubsequência ordenada
2
for (i=3;i<MAX;i++)
4º Passo :Æ Encontrar (selecionar) o menor elemento no array, entre 
as posições [3,Max-1] e colocá-lo na posição 3;
A
r
r
a
y
s
 
–
O
r
d
e
n
a
ç
ã
o
Método de Seleção
Após a execução desse passo:
Descrição do algoritmo:
x x x x x x x x x x x x x x x x
Subsequência não-ordenadaSubsequência ordenada
3
for (i=4;i<MAX;i++)
K-ésimo Passo :Æ Encontrar (selecionar) o menor elemento no 
array, entre as posições [k-1,Max-1] e colocá-lo na posição k-1;
A
r
r
a
y
s
 
–
O
r
d
e
n
a
ç
ã
o
Método de Seleção
Após a execução desse passo:
Descrição do algoritmo:
x x x x x x x x x x x x x x x x
Subsequência
não-ordenada
Subsequência ordenada
K-1
for (i=k;i<MAX;i++)
…, e assim sucessivamente, até
A
r
r
a
y
s
 
–
O
r
d
e
n
a
ç
ã
o
Método de Seleção
Após a execução desse passo:
Descrição do algoritmo:
x x x x x x x x x x x x x x x x
Toda sequência ordenada
Max-2
(Max-1)º Passo :Æ Encontrar (selecionar) o menor elemento no 
array, entre as posições [Max-2,Max-1] e colocá-lo na posição Max-2;
A
r
r
a
y
s
 
–
O
r
d
e
n
a
ç
ã
o
Método de Seleção
...
lim = Dim-1;
for (i = 0; i < lim; i++) // posição onde deve estar o menor elemento na respectiva iteração 
for (j = i; j < Dim; j++) // encontrando o menor elemento entre as posições não ordenadas
if ( Str[j] < Str[i] ){ // permuta os elementos relativos as posições i e j
aux = Str[i]; 
Str[i] = Str[j];
Str[j] = aux;
}
...
Codificação (usando notação indexada)
Função Troca(Str, i, j)
A
r
r
a
y
s
 
–
O
r
d
e
n
a
ç
ã
o
Método de Seleção
Códigos em C: Três versões com ligeiras variantes
(pequenas mudanças). Códigos em anexo.
A
r
r
a
y
s
 
–
O
r
d
e
n
a
ç
ã
o
Método de Bubblesort (Bolha)
x
x
x
x
x
x
x
.
.
.
x
x
x
x
x
xMAX-1
0
1
2
Mais densos
Menos densosIdéia Intuitiva:
A
r
r
a
y
s
 
–
O
r
d
e
n
a
ç
ã
o
Método de Bubblesort (Bolha)
Idéia Intuitiva:
Imaginar um array na vertical e os elementos a serem ordenados 
(números), como sendo partículas/objetos/bolhas com diferentes 
densidades. Logo, os objetos mais densos vão em direção a parte 
mais “funda” (final do array), enquanto os objetos de menor 
densidade, vão em direção a “superfície” (início do array), 
encontrando suas respectivas posições.
Questão? Como materializar (“algoritmizar”) essa idéia.
A
r
r
a
y
s
 
–
O
r
d
e
n
a
ç
ã
o
Método de Bubblesort (Bolha)
Concretizando a idéia:
O princípio associado ao Método da Bolha é comparar elementos em 
posições adjacentes (consecutivas) e trocar os elementos de 
lugar, se estiverem em posições incorretas (fora de ordem). Essa 
idéia, aplicada repetidas vezes fará com que o array de elementos 
fique completamente ordenado.
A
r
r
a
y
s
 
–
O
r
d
e
n
a
ç
ã
o
Método de Bubblesort (Bolha)
Vejamos:
x x x x x x x x x x x x x x x x
Elementos não ordenados
No momento inicial o array de elementos está completamente 
desordenado (hipótese).
A
r
r
a
y
s
 
–
O
r
d
e
n
a
ç
ã
o
Método de Bubblesort (Bolha)
Após a 1ª iteração (1ª varredura):
Subsequência (provavelmente) não ordenada
maior elemento
x x x x x x x x x x x x x x x x
Na primeira iteração, comparamos os elementos associados as 
seguintes posições:
(0,1), (1,2), (2,3), (3,4), ..., (Max-2,Max-1)
Além disso, houve uma movimentação significativa nas posições 
ocupadas pelos elementos. 
A
r
r
a
y
s
 
–
O
r
d
e
n
a
ç
ã
o
Método de Bubblesort (Bolha)
Após a 2ª iteração (2ª varredura):
2º maior elemento
x x x x x x x x x x x x x x x x
Na segunda iteração, comparamos os pares de elementos 
associados as seguintes posições:
(0,1), (1,2), (2,3), (3,4), ..., (Max-3,Max-2)
Novamente, muitas movimentações ocorreram nas posições 
ocupadas pelos elementos. 
Subsequência (provavelmente) não ordenada
A
r
r
a
y
s
 
–
O
r
d
e
n
a
ç
ã
o
Método de Bubblesort (Bolha)
Após a 3ª iteração (3ª varredura):
3º maior elemento
x x x x x x x x x x x x x x x x
Na terceira iteração, comparamos os pares de elementos associados 
as seguintes posições:
(0,1), (1,2), (2,3), (3,4), ..., (Max-4,Max-3)
Novamente, muitas movimentações ocorreram nas posições 
ocupadas pelos elementos. 
Subsequência (provavelmente) não ordenada
A
r
r
a
y
s
 
–
O
r
d
e
n
a
ç
ã
o
Método de Bubblesort (Bolha)
Após a kª iteração (kª varredura):
kº maior elemento
K-elementos ordenados
x x x x x x x x x x x x x x x x
Na k-ésima iteração, comparamos os pares de elementos associados 
as seguintes posições:
(0,1), (1,2), (2,3), (3,4), ..., (Max-k-1,Max-k)
Subsequência (provavelmente) não ordenada
A
r
r
a
y
s
 
–
O
r
d
e
n
a
ç
ã
o
Método de Bubblesort (Bolha)
E assim sucessivamente até a (Max-1)ª iteração ( (Max-1)ª
varredura), quando o array estará completamente ordenado:
Menor Elemento
Subsequência com (Max-1)-elementosordenados
x x x x x x x x x x x x x x x x
Após a (Max-1)ª iteração :
A
r
r
a
y
s
 
–
O
r
d
e
n
a
ç
ã
o
Método de Bubblesort (Código 01)
Organizando as idéias em código (notação indexada). 
...
for(i=1; i<Max; i++)
for(j=0; j<(Max-i); j++)
if (A[j+1] < A[j] )
Troca(A[j],A[j+1]);
...
// i-ésima iteração (número de varreduras)
// índice usado para comparar elementos de diferentes posições
// elementos em posições adjacentes
// trocando elementos nas respectivas posições
Supondo que os dados estejam numa variável estruturada homogênea A. 
A
r
r
a
y
s
 
–
O
r
d
e
n
a
ç
ã
o
Método de Bubblesort (Código 02)
Criando uma função e usando aritmética de ponteiros. 
void Ordenacao_Bolha1(int *A, int Dim) {
int i, j;
for(i=1; i<Dim; i++)
for(j=0; j<(Dim-i); j++)
if ( *(A+j+1) < *(A+j) )
Troca(A, j, j+1);
return;
} // OrdenaçãoBolha1
// i-ésima iteração / número de varreduras
// índice usado para comparar elementos
// elementos em posições adjacentes
// trocando elementos nas respectivas posições
Códigos em anexo.
A
r
r
a
y
s
 
–
O
r
d
e
n
a
ç
ã
o
Método de Bubblesort (Exemplo)
EXERCÍCIO: Na descrição apresentada, a varredura dos elementos é
feita da esquerda para a direita. Reescreva o código, de modo que a 
varredura seja feita da direita para a esquerda. Dessa forma, em cada 
iteração, o menor elemento será colocado em sua posição correta. 
A
r
r
a
y
s
 
–
O
r
d
e
n
a
ç
ã
o
Método de Bubblesort (Exemplo)
OBSERVAÇÕES:
¾ É fácil perceber que ocorre uma movimentação muito grande de dados 
após cada uma das iterações. Isto significa que muitos elementos 
tendem a ocupar suas posições definitivas ou, “muito próximo” delas;
¾ A partir da observação acima, pode ocorrer que após algumas 
iterações o array esteja completamente ordenado, logo, nessa situação, 
não seriam necessários (Max-1) iterações para garantirmos a completa 
ordenação da sequência de valores armazenadas no array.
¾ O exemplo a seguir ilustra esse fato. 
A
r
r
a
y
s
 
–
O
r
d
e
n
a
ç
ã
o
Método de Bubblesort (Exemplo)
15 31 21 17 51 72 93 103 121 157
Vamos considerar a sequência arbitrária de 10 elementos inteiros abaixo, 
armazenada numa estrutura de array e aplicar a ela o método da Bolha. 
0 1 2 3 4 5 6 7 8 9
É fácil observar que há poucos elementos fora de suas posições e, 
aqueles que não estão em suas posições corretas, estão muito próximo 
delas.
Conforme já vimos, será que seriam necessárias (MAX -1) iterações no 
loop externo (slide 25) para uma completa ordenação dessa sequência?
A
r
r
a
y
s
 
–
O
r
d
e
n
a
ç
ã
o
Método de Bubblesort (Exemplo)
15 31 21 17 51 72 93 103 121 157
Após a primeira iteração. 
0 1 2 3 4 5 6 7 8 9
sequência original:
15 21 17 31 51 72 93 103 121 157
0 1 2 3 4 5 6 7 8 9
A
r
r
a
y
s
 
–
O
r
d
e
n
a
ç
ã
o
Método de Bubblesort (Exemplo)
Após a segunda iteração. 
sequência anterior:
15 21 17 31 51 72 93 103 121 157
0 1 2 3 4 5 6 7 8 9
15 17 21 31 51 72 93 103 121 157
0 1 2 3 4 5 6 7 8 9
Na verdade, apenas duas varreduras foram necessárias (loop exterior). Essas 
observações podem ser exploradas para a elaboração de uma outra versão do 
Método da Bolha, computacionalmente mais eficiente.
A
r
r
a
y
s
 
–
O
r
d
e
n
a
ç
ã
o
Método de Bubblesort (Código 03)
void Ordenacao_Bolha1(int *A, int Dim) {
int i=1, j, continua = 1;
while( (i < Dim) && continua ) {
continua = 0;
for(j=0; j < (Dim-i); j++)
if ( *(A+j+1) < *(A+j) ) {
Troca(A, j, j+1);
continua = 1;
}
} // while
return;
} // OrdenaçãoBolha1
A variável continua será
usada para indicar se os 
elementos trocaram de 
posição. Se numa iteração 
qualquer não houver troca, 
então a sequência já está
ordenada. 
A
r
r
a
y
s
 
–
O
r
d
e
n
a
ç
ã
o
Trabalhos Práticos
Códigos em C: Três versões com ligeiras variantes (pequenas
mudanças). Códigos em anexo.
Trabalho envolvendo conjuntos e ordenação.
(Texto em anexo)
Trabalho envolvendo Polinômios e ordenação.
(Texto em anexo)
A
r
r
a
y
s
 
–
O
r
d
e
n
a
ç
ã
o
Observações
Estudar atentamente todos os códigos que foram 
passados a todos vocês. Em breve estaremos 
realizando uma prova sobre arrays uni e 
bidimensionais.