AEDII-aula04

Prévia do material em texto

1
Aula 04 – Limite assintótico para a 
ordenação, Ordenação em tempo linear
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
Os métodos de ordenação são classificados em 2 grande 
grupos:
Ordenação Interna:
Se o arquivo a ser ordenado cabe todo na memória principal
Ordenação Externa:
Se o arquivo a ser ordenado não cabe todo na memória principal
4
Ordenação
Os métodos de ordenação são classificados em 2 grande 
grupos:
Ordenação Interna:
Se o arquivo a ser ordenado cabe todo na memória principal
→ Algoritmos Baseados em Comparações
→ Algoritmos Não Baseados em Comparações
5
Ordenação baseada em comparações
6
Ordenação
Algoritmos basedos em Comparações
Insertion sort
Selection sort
Bubble sort
Merge sort
Quick sort
Complexidade computacional 
[limite matemático]
[limite assintótico para a ordenação]
7
Ordenação baseada em comparações
Sem perda de generalidade suponha que os valores a ser 
ordenados são sempre distintos
[Árvore de decisão]
8
Ordenação baseada em comparações
Sem perda de generalidade suponha que os valores a ser 
ordenados são sempre distintos
[Árvore de decisão]
[Cada nó folha está associada a uma permutação dos elementos do vetor]
9
Ordenação baseada em comparações
Sem perda de generalidade suponha que os valores a ser 
ordenados são sempre distintos
[Árvore de decisão]
[Qualquer algoritmo de ordenação deverá percorrer um caminho desta árvore]
da raiz até a folha
10
Ordenação baseada em comparações
Sem perda de generalidade suponha que os valores a ser 
ordenados são sempre distintos
[Árvore de decisão]
[Qualquer algoritmo de ordenação deverá percorrer um caminho desta árvore]
da raiz até a folha
Número de folhas = n!
11
Ordenação baseada em comparações
Seja L o número de folhas de uma árvore binária e h sua altura.
Então
h=3
L=8
12
Ordenação baseada em comparações
Seja L o número de folhas de uma árvore binária e h sua altura.
Então
h=3
L=8
13
Ordenação baseada em comparações
Seja L o número de folhas de uma árvore binária e h sua altura.
Então
h=3
L=8
14
Ordenação baseada em comparações
Algoritmos basedo em Comparaçães
Insertion sort
Selection sort
Bubble sort
Merge sort
Quick sort
Vários algoritmos aqui listados são ótimos pois a sua 
complexidade computacional é 
15
Ordenação em tempo linear
16
Ordenação
Algoritmos basedo em Comparações
Insertion sort
Selection sort
Bubble sort
Merge sort
Quick sort
Algoritmos não baseados em Comparações
(utilizam alguma informação sobre os dados)
Counting sort
Radix sort
Bin sort / Bucket sort
Algoritmos que fazem a ordenação em tempo linear
17
Counting sort
Os elementos a serem ordenados são números inteiros 
“pequenos”
Números inteiros todos menores ou iguais a k,
18
Counting sort
Os elementos a serem ordenados são números inteiros 
“pequenos”
Números inteiros todos menores ou iguais a k,
Counting sort ordena estes n números em tempo 
Exemplo:
→ n = 1 000 000
→ k = 30
19
Counting sort
O algoritmo usa dois vetores auxiliares para ordenar A:
C (de tamanho k), que guarda em C[i] o número de 
ocorrencias de elementos i em A.
B (de tamanho n), onde se constroi o vetor ordenado.
Simulação:
https://www.cs.usfca.edu/~galles/visualization/CountingSort.html
20
Counting sort
A
C
B
21
Counting sort
A
C
B
22
Counting sort
A
C
B
23
Counting sort
A
C
B
24
Counting sort
A
C
B
25
Counting sort
A
C
B
26
Counting sort
A
C
B
27
Counting sort
A
C
B
28
Counting sort
A
C
B 10
29
Counting sort
A
C
B 10
16
30
Counting sort
A
C
B 3010
31
Counting sort
A
C
B 30
29
10
32
Counting sort
Esboçe o algoritmo! (7 min)
C (de tamanho k), que guarda em C[i] o número de 
ocorrencias de elementos i em A.
B (de tamanho n), onde se constroi o vetor ordenado.
33
Counting sort
34
Counting sort
35
Counting sort
36
Counting sort
M: número de 
movimentações de registros
37
Counting sort
O Counting sort é um algoritmo que faz a ordenação de 
forma estável:
A posição relativa de elementos iguais que ocorrem 
no vetor ordenado permanecem na mesma ordem em 
que aparecem na entrada.
→ Counting sort e Quick sort são estáveis
→ Heap sort não é estável.
38
Counting sort
A
C
B 1010
39
Radix sort
Ordena o vetor A de n números inteiros com um número 
constante d de digitos
A ordem começa pelo digito menos significativo.
Simulação: https://www.cs.usfca.edu/~galles/visualization/RadixSort.html
40
Radix sort
A complexidade computacional, considerando o número de 
movimentações de registros, e o counting sort:
Counting sort = 
Merge sort = 
← Vantajoso quando d<log(n)
41
Bucket sort (Ordenação por balde)
Possui tempo linear, desde que os valores a serem 
ordenados sejam distribuídos uniformemente sobre o 
intervalo [0, 1).
Divide o intervalo [0, 1) em n sub-intervalos iguais, 
denominados buckets (baldes), e então distribui os n 
números reais nos n buckets.
Como a entrada é composta por dados distribuídos 
uniformemente, espera-se que cada balde possua, ao final 
deste processo, um número equivalente de elementos 
(usualmente 1).
42
Bucket sort (Ordenação por balde)
43
Bucket sort (Ordenação por balde)
Cada elemento A[i] satisfaz 0 ≤ A[i] < 1.
Para obter o resultado, basta ordenar os elementos em cada 
bucket e então apresentá-los em ordem
Simulação: https://www.cs.usfca.edu/~galles/visualization/BucketSort.html
44
Atividade bônus: radixsort (7/julho - 23h50)
Implemente o algoritmo Radix sort
Esta atividade é valida para quem não enviou (não enviará) 
um Exercício-Programa.
Os arquivos que deverá submeter pelo Tidia são:
Código fonte em C/C++
(radixsort-RA.cpp)
Um PDF contendo um exemplo de execução 
(radixsort-RA.pdf)
Nota: o formato desse relatório é livre.
	Slide 1
	Slide 2
	Slide 3
	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 32
	Slide 33
	Slide 34
	Slide 36
	Slide 37
	Slide 39
	Slide 40
	Slide 41
	Slide 42
	Slide 43
	Slide 44