Aula 21 Heap Sort e Shell Sort (1)

Prévia do material em texto

Algoritmos e Estruturas de Dados I
Lucas Matsueda
 Heap Sort ou Ordenação usando heap
 Heap: vetor que simula uma árvore binária completa (exceçãodo último nível)
 Todo elemento pai do vetor possui dois elementos como filhos
 Pai (i) -> filhos: (2*i+1) e (2*i+2)
 Em um heap os pais são maiores que seus filhos
 A ideia é transformar um vetor em um heap máximo e depoispegar o maior elemento do heap e colocar na sua posiçãocorrespondente no vetor.
23 4 67 -8 90 54 21
23 4 67 -8 90 54 21 90 23 67 -8 4 54 21
Pai tem dois filhos?Quem é o maior?
Filho maior que o pai?Filho se torna o paiRepetir o processo
Antigo pai ocupa o lugar doúltimo filho analisado
23 4 67 -8 90 54 21vet
i f0 6
0 1 2 3 4 5 6 
23 4 67 -8 90 54 21vet
i f0 6
aux 23
0 1 2 3 4 5 6 
23 4 67 -8 90 54 21vet
i f0 6
aux 23 j 1
0 1 2 3 4 5 6 
23 4 67 -8 90 54 21vet
i f0 6
aux 23 j 1
0 1 2 3 4 5 6 
23 4 67 -8 90 54 21vet
i f0 6
aux 23 j 1
0 1 2 3 4 5 6 
23 4 67 -8 90 54 21vet
i f0 6
aux 23 j 1
0 1 2 3 4 5 6 
vet[1] < vet[2] = 4 < 27 = verdade
23 4 67 -8 90 54 21vet
i f0 6
aux 23 j 2
0 1 2 3 4 5 6 
23 4 67 -8 90 54 21vet
i f0 6
aux 23 j 2
0 1 2 3 4 5 6 
aux < vet[2] = 23 < 67 = verdade
23 4 67 -8 90 54 21vet
i f0 6
aux 23 j 2
0 1 2 3 4 5 6 
vet[0] = vet[2] -> vet[0] = 67
67 4 67 -8 90 54 21vet
i f0 6
aux 23 j 2
0 1 2 3 4 5 6 
vet[0] = vet[2] -> vet[0] = 67
67 4 67 -8 90 54 21vet
i f2 6
aux 23 j 2
0 1 2 3 4 5 6 
67 4 67 -8 90 54 21vet
i f2 6
aux 23 j 5
0 1 2 3 4 5 6 
67 4 67 -8 90 54 21vet
i f2 6
aux 23 j 5
0 1 2 3 4 5 6 
67 4 67 -8 90 54 21vet
i f2 6
aux 23 j 5
0 1 2 3 4 5 6 
67 4 67 -8 90 54 21vet
i f2 6
aux 23 j 5
0 1 2 3 4 5 6 
vet[5] < vet[6] = 54 < 21 = falso
67 4 67 -8 90 54 21vet
i f2 6
aux 23 j 5
0 1 2 3 4 5 6 
aux< vet[5] = 23 < 54 = verdadeiro
67 4 67 -8 90 54 21vet
i f2 6
aux 23 j 5
0 1 2 3 4 5 6 
vet[2] = vet[5] -> vet[2] = 54
67 4 54 -8 90 54 21vet
i f2 6
aux 23 j 5
0 1 2 3 4 5 6 
vet[2] = vet[5] -> vet[2] = 54
67 4 54 -8 90 54 21vet
i f5 6
aux 23 j 5
0 1 2 3 4 5 6 
67 4 54 -8 90 54 21vet
i f5 6
aux 23 j 11
0 1 2 3 4 5 6 
67 4 54 -8 90 54 21vet
i f5 6
aux 23 j 11
0 1 2 3 4 5 6 
Falso!!!
67 4 54 -8 90 54 21vet
i f5 6
aux 23 j 11
0 1 2 3 4 5 6 
vet[5] = aux -> vet[5] = 23
67 4 54 -8 90 23 21vet
i f5 6
aux 23 j 11
0 1 2 3 4 5 6 
vet[5] = aux -> vet[5] = 23
67 4 54 -8 90 23 21vet
i f5 6
aux 23 j 11
0 1 2 3 4 5 6 
vet[5] = aux -> vet[5] = 23
67 4 54 -8 90 23 21
É um heap?
67 4 54 -8 90 23 21
É um heap? Não
23 4 67 -8 90 54 21
23 4 67 -8 90 54 21
i 3
heapSort(vet, 7);
23 4 67 -8 90 54 21
i 3
heapSort(vet, 7);
criaHeap(vet, 3, 6);
23 4 67 -8 90 54 21
i 2
heapSort(vet, 7);
criaHeap(vet, 2, 6);
23 4 67 -8 90 54 21
i 1
heapSort(vet, 7);
criaHeap(vet, 1, 6);
23 90 67 -8 4 54 21
i 1
heapSort(vet, 7);
criaHeap(vet, 1, 6);
i 0
heapSort(vet, 7);
criaHeap(vet, 0, 6);
23 90 67 -8 4 54 21
i 0
heapSort(vet, 7);
criaHeap(vet, 0, 6);
90 23 67 -8 4 54 21
i 0
heapSort(vet, 7);
criaHeap(vet, 0, 6);
90 23 67 -8 4 54 21
Cria heap a partir dos dados
Cria heap a partir dos dados
Pegar o maior elemento daheap e colocar na suaposição correspondente novetor
Reconstruir heap
Cria heap a partir dos dados
Pegar o maior elemento daheap e colocar na suaposição correspondente novetor
Reconstruir heap
23 4 67 -8 90 54 21 90 23 67 -8 4 54 21
23 4 67 -8 90 54 21 90 23 67 -8 4 54 21
i 6
0 1 2 3 4 5 6 
23 4 67 -8 90 54 21 90 23 67 -8 4 54 21
i 6
0 1 2 3 4 5 6 
23 4 67 -8 90 54 21 21 23 67 -8 4 54 90
i 6
0 1 2 3 4 5 6 
23 4 67 -8 90 54 21 21 23 67 -8 4 54 90
i 6
0 1 2 3 4 5 6 
23 4 67 -8 90 54 21 21 23 67 -8 4 54 90
i 6
0 1 2 3 4 5 6 
Reorganizar!!
23 4 67 -8 90 54 21 67 23 54 -8 4 21 90
i 6
0 1 2 3 4 5 6 
Reorganizar!!
23 4 67 -8 90 54 21 67 23 54 -8 4 21 90
i 5
0 1 2 3 4 5 6 
23 4 67 -8 90 54 21 67 23 54 -8 4 21 90
i 5
0 1 2 3 4 5 6 
23 4 67 -8 90 54 21 21 23 54 -8 4 67 90
i 5
0 1 2 3 4 5 6 
23 4 67 -8 90 54 21 21 23 54 -8 4 67 90
i 5
0 1 2 3 4 5 6 
23 4 67 -8 90 54 21 54 23 21 -8 4 67 90
i 5
0 1 2 3 4 5 6 
23 4 67 -8 90 54 21 54 23 21 -8 4 67 90
i 4
0 1 2 3 4 5 6 
23 4 67 -8 90 54 21 54 23 21 -8 4 67 90
i 4
0 1 2 3 4 5 6 
23 4 67 -8 90 54 21 4 23 21 -8 54 67 90
i 4
0 1 2 3 4 5 6 
23 4 67 -8 90 54 21 4 23 21 -8 54 67 90
i 4
0 1 2 3 4 5 6 
23 4 67 -8 90 54 21 23 4 21 -8 54 67 90
i 4
0 1 2 3 4 5 6 
23 4 67 -8 90 54 21 21 4 -8 23 54 67 90
i 3
0 12 3 4 5 6 
23 4 67 -8 90 54 21 4 -8 21 23 54 67 90
i 2
0 1 2 3 4 5 6 
23 4 67 -8 90 54 21 -8 4 21 23 54 67 90
i 1
0 1 2 3 4 5 6 
23 4 67 -8 90 54 21 -8 4 21 23 54 67 90
i 0
0 1 2 3 4 5 6 
23 4 67 -8 90 54 21 -8 4 21 23 54 67 90
i 0
0 1 2 3 4 5 6 
Não é estável
 É uma extensão do Insertion Sort
 Insertion Sort: Troca itens adjacentes para determinar o ponto de inserção.
 São efetuadas n - 1 comparações e movimentações quando o menor item está na posição mais à direita no vetor.
O método de Shell contorna este problema permitindo trocas de registros distantes um do outro (GAP).
Os itens separados de h posições são rearranjados.
Todo h-ésimo item leva a uma seqüência ordenada.
Tal sequência é dita estar h-ordenada.
Depois, o valor de h é reduzido progressivamente, atéatingir o valor 1, que resultará no vetor completamenteordenado
6 5 2 1 4 7 3 8vet 0 1 2 3 4 5 6 7 GAP 4
6 5 2 1 4 7 3 8vet 0 1 2 3 4 5 6 7 
4 5 2 1 6 7 3 8vet 0 1 2 3 4 5 6 7 
GAP 4
GAP 2
6 5 2 1 4 7 3 8vet 0 1 2 3 4 5 6 7 
4 5 2 1 6 7 3 8vet 0 1 2 3 4 5 6 7 
2 1 3 5 4 7 6 8vet 0 1 2 3 4 5 6 7 
GAP 4
GAP 2
GAP 1
6 5 2 1 4 7 3 8vet 0 1 2 3 4 5 6 7 
4 5 2 1 6 7 3 8vet 0 1 2 3 4 5 6 7 
2 1 3 5 4 7 6 8vet 0 1 2 3 4 5 6 7 
1 2 3 4 5 6 7 8vet 0 1 2 3 4 5 6 7 
GAP 4
GAP 2
GAP 1
6 5 2 1 4 7 3 8
size 8
vet
0 1 2 3 4 5 6 7 
6 5 2 1 4 7 3 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
6 5 2 1 4 7 3 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 8
6 5 2 1 4 7 3 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 8
6 5 2 1 4 7 3 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 4
6 5 2 1 4 7 3 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 4
6 5 2 1 4 7 3 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 4
4
6 5 2 1 4 7 3 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 4
4 4
6 5 2 1 4 7 3 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 4
4 40
6 5 2 1 4 7 3 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 4
4 40
4 < 6
6 5 2 1 4 7 3 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 4
4 40
vet[4] = vet[0] -> vet[4] = 6
6 5 2 1 6 7 3 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 4
4 40
vet[4] = vet[0] -> vet[4] = 6
6 5 2 1 6 7 3 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 4
4 40
6 5 2 1 6 7 3 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 4
4 4-4
6 5 2 1 6 7 3 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 4
4 4-4
6 5 2 1 6 7 3 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 4
4 4-4
vet[0] = value -> vet[0] = 4
4 5 2 1 6 7 3 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 4
4 4-4
vet[0] = value -> vet[0] = 4
4 5 2 1 6 7 3 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 4
5 4-4
4 5 2 1 6 7 3 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 4
5 7-4
4 5 2 1 6 7 3 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 4
5 71
4 5 2 1 6 7 3 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 4
5 71
7 < 5
4 5 2 1 6 7 3 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 4
5 71
vet[5] = value -> vet[5] = 7
4 5 2 1 6 7 3 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 4
6 71
4 5 2 1 6 7 3 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 4
6 31
4 5 2 1 6 7 3 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 4
6 32
4 5 2 1 6 7 3 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 4
6 32
3 < 2
4 5 2 1 6 7 3 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 4
7 83
8 < 1
4 5 2 1 6 7 3 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 4
8 83
8 < 1
Falso!
4 5 2 1 6 7 3 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 4
8 83
4 5 2 1 6 7 3 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 2
8 83
4 5 2 1 6 7 3 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 2
2 83
4 5 2 1 6 7 3 8
size 8
vet
0 1 2 3 4 56 7 
i j value
gap 2
2 23
4 5 2 1 6 7 3 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 2
2 20
4 5 2 1 6 7 3 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 2
2 20
2 < 4
2 5 4 1 6 7 3 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 2
2 20
2 < 4
2 5 4 1 6 7 3 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 2
3 20
2 5 4 1 6 7 3 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 2
3 10
2 5 4 1 6 7 3 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 2
3 11
2 5 4 1 6 7 3 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 2
3 11
1 < 5
2 1 4 5 6 7 3 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 2
3 11
1 < 5
2 1 4 5 6 7 3 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 2
4 62
6 < 4
2 1 4 5 6 7 3 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 2
5 73
7 < 5
2 1 4 5 6 7 3 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 2
6 34
2 1 4 5 6 7 3 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 2
6 34
3 < 6
2 1 4 5 6 7 3 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 2
6 34
vet[6] = vet[4] -> vet[6] = 6
2 1 4 5 6 7 6 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 2
6 34
vet[6] = vet[4] -> vet[6] = 6
2 1 4 5 6 7 6 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 2
6 32
2 1 4 5 6 7 6 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 2
6 32
3 < 4
2 1 4 5 6 7 6 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 2
6 32
vet[4] = vet[2] -> vet[4] = 4
2 1 4 5 4 7 6 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 2
6 30
vet[4] = vet[2] -> vet[4] = 4
2 1 4 5 4 7 6 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 2
6 30
3 < 2
2 1 4 5 4 7 6 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 2
6 30
vet[2] = value -> vet[2] = 3
2 1 3 5 4 7 6 8
size 8
vet
0 1 2 3 4 5 6 7 
i j value
gap 2
6 30
vet[2] = value -> vet[2] = 3
1 2 3 4 5 6 7 8vet 0 1 2 3 4 5 6 7 
gap 1
1 2 3 4 5 6 7 8vet 0 1 2 3 4 5 6 7 
gap 1
Não é estável
 CORMEM, T.; ET. AL; Algoritmos: teoria e prática. Editora Campus, 2002.
 http://lucasmatsueda.wix.com/lucasmatsueda