Algoritmos de Ordenação de Arrays

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
¾ seqüê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. 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;
¾ Base de fichas catalográficas (biblioteca), 
…, etc.
Algoritmo de
Ordenação
A
r
r
a
y
s
 
–
O
r
d
e
n
a
ç
ã
o
Idéias Gerais
¾ Interna:
¾ Externa: Outras disciplinas
ƒ Seleção;
ƒ Inserção;
ƒ BubbleSort (Bolha);
ƒ ShellSort;
ƒ MergeSort;
ƒ QuickSort;
ƒ…..
Onde: C: Conjunto/Coleção armazenados numa estrutura de array e 
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
Método de Seleçã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
=
≤ ∀ ≤ < ≤
"
A
r
r
a
y
s
 
–
O
r
d
e
n
a
ç
ã
o
Método de Seleçã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!
A
r
r
a
y
s
 
–
O
r
d
e
n
a
ç
ã
o
Método de Seleçã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}. 
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 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
Subseqüência não-ordenadaSubseqüência ordenada
0
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
Subseqüência não-ordenadaSubseqüência ordenada
1
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
Subseqüência não-ordenadaSubseqüência ordenada
2
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
Subseqüência não-ordenadaSubseqüência ordenada
3
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
Subseqüência
não-ordenada
Subseqüência ordenada
k
…, 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 seqüê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
Códigos em C: Três versões com ligeiras variantes (pequenas
mudanças), em anexo a aula.
Trabalho envolvendo conjuntos e ordenação.
(Texto em anexo)
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), em anexo a aula.
Trabalho envolvendo conjuntos e ordenação.
(Texto 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
xn-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 “fundo” (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.
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):
Elementos não ordenados
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):
Elementos não ordenados
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. 
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):
Elementos não ordenados
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. 
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):
Elementos não ordenados
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)
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
(Max-1)-elementos ordenados
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(j,j+1);
...
// i-ésima iteração (número de varreduras)
// índice usado para comparar elementos
// elementos em posições adjacentes
// trocando elementos nas respectivas posições
Supondo que os dados estejamnuma 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
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:
¾ Se formos um pouco mais cuidadosos, iremos perceber que ocorre 
uma grande movimentação 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 seqüê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 seqüê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 seqüê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
Seqüê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. 
Seqüê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 
seqüência já está
ordenada. 
A
r
r
a
y
s
 
–
O
r
d
e
n
a
ç
ã
o
Método de Bubblesort (Códigos)
Estudar atentamente todos os códigos que foram 
passados a todos vocês. Em breve estaremos 
realizando uma prova sobre arrays unidimensionais.