Aula 2 - Ordenação

Prévia do material em texto

UFU/FACOM/ED2/Ordenação
Prof.Autran Macêdo
1 / 452011
Introdução
● Ordenação
– É a tarefa de colocar um conjunto de 
dados em uma determinada ordem.
● Algoritmos de ordenação ou sort
– Vamos estudar algoritmos 
● básicos O(N2) e 
● sofisticados O(NlogN),
– onde N corresponde à quantidade de dados a serem 
ordenados.
UFU/FACOM/ED2/Ordenação
Prof.Autran Macêdo
2 / 452011
Introdução
● Por que estudar os algoritmos 
básicos?
– Fácil implementação
– Desempenho
● Superior aos dos algoritmos complexos, em 
algumas situações;
● Melhoram o desempenho dos alg.complexos.
– Auxiliam o entendimento dos algoritmos 
complexos.
UFU/FACOM/ED2/Ordenação
Prof.Autran Macêdo
3 / 452011
Introdução
● A ordenação pode ocorrer em dois 
contextos:
– memória (ordenação interna);
– disco (ordenação externa).
● A ordenação leva em consideração um 
campo que é conhecido como chave.
UFU/FACOM/ED2/Ordenação
Prof.Autran Macêdo
4 / 452011
Introdução
● Considere os seguintes itens
– João, SP
– Pedro, DF
– Carlos, SP
● Qual é o resultado da ordenação 
desses itens a partir da UF?
UFU/FACOM/ED2/Ordenação
Prof.Autran Macêdo
5 / 452011
Introdução
● Observe os possíveis resultados
– Pedro, DF
– Carlos, SP
– João, SP
– Pedro, DF
– João, SP
– Carlos, SP
Ordenção
Instável
Ordenção
Estável
UFU/FACOM/ED2/Ordenação
Prof.Autran Macêdo
6 / 452011
Introdução
● Propriedade
– “Um método de ordenação é dito estável 
se ele preserva a ordem dos itens com 
chave duplicada.”
● Alguns algoritmos são estáveis (ex: 
inserção, bolha).
UFU/FACOM/ED2/Ordenação
Prof.Autran Macêdo
7 / 452011
Introdução
● A estabilidade pode ser obtida
● mais tempo
● mais memória
● Vejamos alguns algoritmos básicos.
● Considere ordenação ascendente.
UFU/FACOM/ED2/Ordenação
Prof.Autran Macêdo
8 / 452011
Seleção
● “Encontre o item com a menor chave 
e coloque-o na 1a posição. Em 
seguida, encontre a 2a menor chave 
e assim por diante.”
● Vejamos um exemplo
UFU/FACOM/ED2/Ordenação
Prof.Autran Macêdo
9 / 452011
Seleção
15 5 4 3 6
15 5 4 3 6
 3 5 4 15 6
 3 5 4 15 6
 3 4 5 15 6
 3 4 5 15 6
 3 4 5 15 6
 3 4 5 15 6
 3 4 5 6 15
 3 4 5 6 15
UFU/FACOM/ED2/Ordenação
Prof.Autran Macêdo
10 / 452011
Alguns defines
#define less(A, B) (key(A) < key(B))
#define key(A) (A)
#define exch(A, B){Item t = A; A = B; B = t;}
#define compexch(A, B) if (less(B, A)) exch(A, 
B)
UFU/FACOM/ED2/Ordenação
Prof.Autran Macêdo
11 / 452011
Seleção
// ordena a[] entre as posicoes l e r
void selection (Item a[], int l, int r) {
 int i, j;
 for (i = l; i < r; i++) {
 int min = i;
 for (j = i + 1; j <= r; j++)
 if (less (a[j], a[min])) min = j;
 exch (a[i], a[min]);
 }
}
UFU/FACOM/ED2/Ordenação
Prof.Autran Macêdo
12 / 452011
Seleção
● Quando usar
– Itens “grandes”
● Evite usar
– Arquivos já ordenados
– Arquivo com muitas chaves em duplicata
UFU/FACOM/ED2/Ordenação
Prof.Autran Macêdo
13 / 452011
Inserção
● Você já colocou as cartas do 
baralho de sua mão em ordem?
– “Pega-se uma carta de cada vez e a 
coloca em seu devido lugar, sempre 
deixando as cartas da mão em ordem.”
– Vejamos um exemplo
UFU/FACOM/ED2/Ordenação
Prof.Autran Macêdo
14 / 452011
Inserção
Recebe a carta 15
Recebe a carta 5
Recebe a carta 4
Recebe a carta 3
Recebe a carta 6
15
 5 15
 4 5 15
 3 4 5 15
 3 4 5 6 15
Como realizar esse procedimento em um vetor?
●
 Não há visão global das “cartas”
UFU/FACOM/ED2/Ordenação
Prof.Autran Macêdo
15 / 452011
Inserção
15 5 4 3 6
15 5 4 3 6 
 5 15 4 3 6
 5 4 15 3 6
 4 5 15 3 6
 4 5 3 15 6
 
 4 3 5 15 6
 3 4 5 15 6
 3 4 5 15 6
 3 4 5 6 15
UFU/FACOM/ED2/Ordenação
Prof.Autran Macêdo
16 / 452011
Inserção
// ordena a[] entre as posicoes l e r
void insertion (Item a[], int l, int r) {
 int i;
 for (i = l + 1; i <= r; i++) compexch (a[l], 
a[i]);// sentinela
 for (i = l + 2; i <= r; i++) {
 int j = i; Item v = a[i];
 while (less (v, a[j – 1]))
 {a[j] = a[j – 1]; j--;}
 a[j] = v;
 }
}
UFU/FACOM/ED2/Ordenação
Prof.Autran Macêdo
17 / 452011
Inserção
● Quando usar
● Arquivos (quase) ordenados
UFU/FACOM/ED2/Ordenação
Prof.Autran Macêdo
18 / 452011
Bolha
● Você já observou uma panela 
fervendo?
– As “bolhas” se debatem e as mais leves 
(quentes) sobem.
● “Compara-se dois itens; o menor (ou 
maior) troca de lugar; o item que 
provocou a troca, agora é comparado 
com seu próximo vizinho.”
UFU/FACOM/ED2/Ordenação
Prof.Autran Macêdo
19 / 452011
Bolha
15 5 4 3 6
15 5 4 3 6
15 5 4 3 6
15 5 3 4 6
15 3 5 4 6
 3 15 5 4 6
 3 15 5 4 6
 3 15 5 4 6
3 15 4 5 6
3 4 15 5 6
3 4 15 5 6
3 4 15 5 6
3 4 5 15 6
3 4 5 15 6
3 4 5 6 15
UFU/FACOM/ED2/Ordenação
Prof.Autran Macêdo
20 / 452011
Bolha
// ordena a[] entre as posicoes l e r
void buble (Item a[], int l, int r) {
 int i, j;
 for (i = l; i < r; i++)
 for (j = r; j > i; j--)
 compexch (a[j-1], a[j]);
}
UFU/FACOM/ED2/Ordenação
Prof.Autran Macêdo
21 / 452011
Bolha
● Quando usar
– Fins acadêmicos
– Arquivos (quase) ordenados, se o 
algoritmo for modificado.
UFU/FACOM/ED2/Ordenação
Prof.Autran Macêdo
22 / 452011
Algoritmos Básicos
● Considerações Finais
– A ordem de complexidade dos algoritmos 
de ordenação são da ordem de O(N2).
– Contudo, esses algoritmos são 
importantes porque
● auxiliam o entendimento de algoritmos mais 
sofisticados;
● superam o desempenho de algortimos 
O(NlogN) em algumas situações.
– Vejamos alguns números.
UFU/FACOM/ED2/Ordenação
Prof.Autran Macêdo
23 / 452011
Algoritmos Básicos
● Considerações Finais
 N = 1000 N = 2000 N = 4000
 S 5 21 85
 I 4 15 62
 B 8 34 138 
 S 13 56 228
 I 8 31 126
 B 19 78 321 
Chave
Int
Chave
String
Seleção
Inserção
Bolha
?!
UFU/FACOM/ED2/Ordenação
Prof.Autran Macêdo
24 / 452011
Algoritmos Básicos
● Considerações Finais
– “O algoritmo Seleção demanda tempo 
linear quando submetido a arquivos com 
itens grandes e chaves pequenas.”
● Seja
– M = (1 – tamChave / tamItem) . tamItem
– 1 compararação = 1 unidade de tempo
– 1 troca = M unidades de tempo
● Se M for grande e M > N
● então f(N.M) domina f(N2)
UFU/FACOM/ED2/Ordenação
Prof.Autran Macêdo
25 / 452011
Shellsort
● Trata-se de uma extensão ao 
algoritmo Inserção.
● A extensão procura colocar um 
elemento mais rapidamente em seu 
lugar.
– No algoritmo Inserção, os saltos 
ocorrem com incrementos de 1.
– No Shellsort, os incrementos são 
maiores do que 1.
UFU/FACOM/ED2/Ordenação
Prof.Autran Macêdo
26 / 452011
Shellsort
● Em outras palavras
– Um elemento x é comparado contra os 
elementos com distância h = q, onde q 
pode ser > 1. 
– A comparação termina quando x encontra 
“seu lugar”.
UFU/FACOM/ED2/Ordenação
Prof.Autran Macêdo
27 / 452011
Shellsort
● (continuação)
– Em seguida, toma-se o elemento vizinho 
de x. Realiza-se então comparações 
entre os elementos com distância h = 
q.
– Quando todos os elementos tiverem sido 
comparados, decrementa-se o valor de h 
e retomam-se as comparações.
UFU/FACOM/ED2/OrdenaçãoProf.Autran Macêdo
28 / 452011
Shellsort
 7 3 5 4 1 12 9 6 7 4 3 9 10 14 3
h=5 7 3 5 4 1 12 9 6 7 4 3 9 10 14 3
 7 3 5 4 1 12 9 6 7 4 3 9 10 14 3
 7 3 5 4 1 12 9 6 7 4 3 9 10 14 3 
 7 3 5 4 1 12 9 6 7 4 3 9 10 14 3 
 7 3 5 4 1 12 9 6 7 4 3 9 10 14 3
 7 3 5 4 1 12 9 6 7 4 3 9 10 14 3
 7 3 5 4 1 3 9 6 7 4 12 9 10 14 3
 3 3 5 4 1 7 9 6 7 4 12 9 10 14 3
 3 3 5 4 1 7 9 6 7 4 12 9 10 14 3
 ...
UFU/FACOM/ED2/Ordenação
Prof.Autran Macêdo
29 / 452011
Shellsort
// ordena a[] entre as posicoes l e r
void shellsort (Item a[], int l, int r) {
 int i, j, h;
 for (h = l; h <= (r – l) / 9; h = 3 * h + 1); // calc h
 for (; h > 0; h /= 3) // a cada iteração decrementa h
 for (i = h + l; i <= r; i++) {
 int j = i; Item v = a[i];
 while (j >= l + h && less (v, a[j – h])) 
 {a[j] = a[j – h]; j -= h;}
 a[j] = v;
 }
}
UFU/FACOM/ED2/Ordenação
Prof.Autran Macêdo
30 / 452011
Shellsort
● O custo do Shellsort ainda não 
está provado.
● O custo depende do valor dos 
incrementos.
– O(N3/2) 1, 4, 13, 40, 121, 364, 
1093, ...
– O(N4/3) 1, 8, 23, 77, 281, 
1073, ...
– O(N(log N)2) 1, 2, 3, 4, 6, 9, 12, 
18, 27, ...
UFU/FACOM/ED2/Ordenação
Prof.Autran Macêdo
31 / 452011
Quicksort
● Proposto por C.A.R. Hoare em 1960
– C.A.R. Hoare: Quicksort. Computer 
Journal, Vol. 5, 1, 10-15 (1962)
– Um dos algoritmos mais estudados.
● Várias propostas de otimização.
UFU/FACOM/ED2/Ordenação
Prof.Autran Macêdo
32 / 452011
Quicksort
● Utiliza a técnica dividir-e-
conquistar.
● Particiona-se o objeto, então 
ordena-se cada partição 
independentemente.
UFU/FACOM/ED2/Ordenação
Prof.Autran Macêdo
33 / 452011
Quicksort
● Importante: encontrar a posição do 
pivô.
– Item que determina partição do 
objeto (vetor).
● Qual item é o pivô?
– Escolhe-se um item do vetor.
– Vamos escolher o último.
UFU/FACOM/ED2/Ordenação
Prof.Autran Macêdo
34 / 452011
Quicksort
● Restrições quanto ao pivô
– Seja i a posição do pivô.
– Os itens anteriores à i possuem 
chave menor ou igual à do pivô.
– Os itens posteriores à i possuem 
chave maior ou igual à do pivô.
UFU/FACOM/ED2/Ordenação
Prof.Autran Macêdo
35 / 452011
Quicksort
15 5 10 8 7 3 4 9
15 5 10 8 7 3 4 9
15 5 10 8 7 3 4 9
 4 5 10 8 7 3 15 9
 4 5 10 8 7 3 15 9
 4 5 10 8 7 3 15 9
 4 5 10 8 7 3 15 9
 4 5 3 8 7 10 15 9
 4 5 3 8 7 10 15 9
 
 4 5 3 8 7 10 15 9
 4 5 3 8 7 10 15 9
 4 5 3 8 7 10 15 9
 4 5 3 8 7 9 15 10 
Pivô no 
lugar
Partições
UFU/FACOM/ED2/Ordenação
Prof.Autran Macêdo
36 / 452011
Quicksort
int partition(Item a[], int l, int r);
void quicksort(Item a[], int l, int r){
 int i;
 if (r <= l) return;
 i = partition(a, l, r);
 quicksort(a, l, i-1);
 quicksort(a, i+1, r);
}
UFU/FACOM/ED2/Ordenação
Prof.Autran Macêdo
37 / 452011
Quicksort
int partition(Item a[], int l, int r) {
 int i = l-1, j = r; Item v = a[r];
 for (;;) {
 while (less(a[++i], v)) ;
 while (less(v, a[--j])) if (j == l) break;
 if (i >= j) break;
 exch(a[i], a[j]);
 }
 exch(a[i], a[r]);
 return i;
}
UFU/FACOM/ED2/Ordenação
Prof.Autran Macêdo
38 / 452011
Quicksort Básico
● Custo
– O(NlogN) comparações na prática.
– No pior caso: O(N2/2) comparações
● Em que circunstâncias o pior caso 
pode ocorrer?
UFU/FACOM/ED2/Ordenação
Prof.Autran Macêdo
39 / 452011
Otimizações para o Quicksort
● Mini-Partição
if ((r – l) < P)
 insertion (a, l, r);
ou
if ((r – l) < P)
 return;
UFU/FACOM/ED2/Ordenação
Prof.Autran Macêdo
40 / 452011
Otimizações para o Quicksort
● Mediana-de-Três
– O pivô é escolhido entre três itens do 
objeto a ser ordenado: o primeiro, o 
do meio, e o último.
● Mini-Partição ☉ Mediana-de-Três 
–
 melhora entre 20% a 25%, com relação 
ao algorimo básico.
UFU/FACOM/ED2/Ordenação
Prof.Autran Macêdo
41 / 452011
Quicksort Otimizado
void sort(Item a[], int l, int r)
 { 
 quicksort(a, l, r);
 insertion(a, l, r);
 }
UFU/FACOM/ED2/Ordenação
Prof.Autran Macêdo
42 / 452011
Quicksort Otimizado
#define M 10
void quicksort(Item a[], int l, int r) {
 int i; 
 if (r-l <= M) return;
 exch(a[(l+r)/2], a[r-1]);
 compexch(a[l], a[r-1]); 
 compexch(a[l], a[r]); 
 compexch(a[r-1], a[r]);
 i = partition(a, l+1, r-1);
 quicksort(a, l, i-1);
 quicksort(a, i+1, r);
} 
Mediana-de-Três
Mini-Partição
UFU/FACOM/ED2/Ordenação
Prof.Autran Macêdo
43 / 452011
Relembrando os Defines
#define less(A, B) (key(A) < key(B))
#define key(A) (A)
#define exch(A, B){Item t = A; A = B; B = t;}
#define compexch(A, B) if (less(B, A)) exch(A, 
B)
UFU/FACOM/ED2/Ordenação
Prof.Autran Macêdo
44 / 452011
Cnsiderações Finais
● Quicksort é o algoritmo a ser 
escolhido se
● a ordenação será realizada na memória;
● não se tem qualquer informação quanto aos 
elementos a serem ordenados.
● Façam o exercício de implementação.
UFU/FACOM/ED2/Ordenação
Prof.Autran Macêdo
45 / 452011
Referências
● Capítulo sobre Ordenação (Sorting) 
em um dos livros textos.
● Código em C
www.cs.princeton.edu/~rs/Algs3.c1-
4/code.txt
chapter 6 (básicos) e 7 (quicksort)
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40
	Slide 41
	Slide 42
	Slide 43
	Slide 44
	Slide 45