AEDII-aula05

Prévia do material em texto

1
Aula 05 – Ordenação parcial
MC3305
Algoritmos e Estruturas de Dados II
Prof. Jesús P. Mena-Chalco
jesus.mena@ufabc.edu.br
2Q-2014
2
Ordenação
Ordenar corresponde ao processo de re-arranjar um 
conjunto de objetos em ordem ascendente ou descendente.
O objetivo principal da ordenação é facilitar a recuperação 
posterior de itens do conjunto ordenado.
Diversos algoritmos de ordenação já foram estudados e 
implementados...
3
Ordenação
Limite assintótico para algoritmos de ordenação baseadas 
em comparações
A ordenação em tempo linear está associada a algoritmos 
que não consideram comparações entre seus elementos
4
Ordenação parcial
5
Ordenação parcial (seleção do k-éssimo maior)
Consiste em obter os k primeiros elementos de um 
arranjo/vetor ordenado com n elementos.
Quando k=1 o problema se reduz a encontrar o mínimo (ou o 
máximo) de um conjunto de elementos.
Quando k=n caímos no problema clássico de ordenação.
6
Ordenação parcial (aplicação)
7
Ordenação parcial (aplicação)
Facilitar a busca de informação na web com as máquinas de 
busa:
É comum uma consulta na web retornar centenas de 
milhares de documentos relacionados com a consulta.
O usuário está interessado em apenas os k mais 
relevantes.
Em geral k<200 documentos.
Normalmente são consultados os 10 primeiros 
documentos.
Assim, são necessários algoritmos de ordenação 
parcial.
8
Ordenação parcial
Os algoritmos de Ord. Parcial que estudaremos serão:
Seleção parcial
Inserção parcial
Heapsort parcial
Quicksort parcial
9
Seleção parcial
10
Seleção parcial
Um dos algoritmos mais simples.
Principio de funcionamento:
Selecione o menor item do vetor.
Troque-o com o item que está na primeira posição do 
vetor.
Repita estas duas operações com os itens:
n-1, n-2, n-3, …, n-(k-1), n-k
Animação: https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html
11
Seleção parcial
12
Seleção parcial
k=7
13
Seleção parcial
Identifique o número de: 
 - Comparações entre elementos
 - Movimentações entre registros
14
Seleção parcial
Identifique o número de: 
 - Comparações entre elementos
 - Movimentações entre registros
Espetacular: Comportamento linear no tamanho de k!
15
Seleção parcial
É “muito” simples de ser obtido a partir da implementação do 
algoritmo de ordenação por seleção.
Possui um comportamento espetacular quanto ao número de 
movimentos de registros:
Tempo de execução é linear no tamanho de k.
16
Inserção parcial
17
Inserção parcial
Pode ser obtido a partir do algoritmo de ordenação por 
Inserção por meio de uma modificação:
Tendo sido ordenado os primeiros k itens, o item da k-
essima posição funciona como um pivô.
Quando o item entre os restantes é menor do que o pivô, 
ele é inserido na posição correta entre os k itens de 
acordo com o algoritmo original.
18
Inserção
Animação: https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html
Método preferido dos jogadores de cartas
Em cada passo, a partir do i=2, o I-ésimo elemento 
da sequência fonte é apanhado e transferido para a 
sequência destino, sendo inserido no seu lugar 
apropriado.
1 5 7 10 55 6
1 5 7 10 55
6
19
Inserção
1 5 7 10 55
6
i=5j=[0,4]
20
Inserção parcial
1 5 7 10 557
i>(k-1)
0 1 2 3 4 5 6 7 8 9 10 11 12
i<=(k-1)
k=6
21
Inserção parcial
1 5 7 10 55
k=6
7
i>(k-1)
0 1 2 3 4 5 6 7 8 9 10 11 12
i<=(k-1)
1 5 7 10 557 -1
i>(k-1)i<=(k-1)
0 1 2 3 4 5 6 7 8 9 10 11 12
22
Inserção parcial
23
Inserção parcial
k=6
24
Inserção parcial
k=6
O algoritmo não preserva o restante do vetor
25
Inserção parcial
- Comparações entre elementos: (melhor caso e pior caso) ?
- Movimentações entre registros: (melhor caso e pior caso) ?
26
Inserção parcial
Comparações entre elementos: 
 - Melhor caso 
 - Pior caso
← n-1 iterações
27
Inserção parcial
Movimentações entre elementos: 
 - Melhor caso 
 - Pior caso
← 1 movimentação
← 1 movimentação
← 1 movimentação
28
Inserção parcial 2 (preserva o restante do vetor)
29
Inserção parcial 2 (preserva o restante do vetor)
k=6
Versão 1
Versão 2
k=6
30
Heapsort parcial
31
Inserção parcial
Utiliza um tipo abstrato de dados heap para informar o menor 
item do conjunto.
Usando um MIN-HEAP
Na primeira iteração, o menor item que está 
em A[0] (raiz do heap) é trocado com o item 
que está em A[n-1].
Em seguida o heap é refeito.
Novamente o menor está em A[0], troque-o 
com A[n-1].
Repita as duas últimas operações até que o k-
ésimo menor esteja seja trocado com A[n-k].
Ao final, os k menores estão nas k últimas 
posições do vetor A.
Animação: https://www.cs.usfca.edu/~galles/visualization/HeapSort.html
32
Inserção parcial
O heapsort-Parcial deve construir o heap a um custo O(n).
O prodecimento Refaz tem um custo de O(lg(n)).
O procedimento heapsort parcial chama o procedimento 
anterior k vezes.
Complexidade: 
33
Quicksort parcial
34
Atividade QuickSort Parcial (18/julho - 23h50)
Implemente o algoritmo Quicksort parcial
http://www2.dcc.ufmg.br/livros/algoritmos-edicao2/cap4/transp/completo1/cap4.pdf
Os arquivos que deverá submeter pelo Tidia são:
Código fonte em C/C++
(quicksortParcial-RA.cpp)
Um PDF contendo um exemplo de execução 
(quicksortParcial-RA.pdf)
Nota: o formato desse relatório é livre. Quando mais completo, melhor.
	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 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34