Dada a sequência de números: 349258217462985 1, ordene-a em ordem não decrescente segundo os seguintes algoritmos, apresentando a sequência obtida após cada passo do algoritmo:
HeapSort

Passo 1

A gente tem a sequência original de 16 elementos: a matéria aqui é HeapSort, que consiste em construir um heap máximo e depois repetir extrações da raiz para ordenação. Vamos precisar usar as operações de heapify (sift-down) e troca de elementos.

Passo 2

Construção do max-heap: a gente aplica heapify a partir de i=lfloor16/2rfloor=8 até i=1. Depois de ajustar cada subárvore, o vetor fica
(9,7,9,4,6,8,8,1,2,4,5,2,3,2,5,1)

Passo 3

Passo k=16: trocamos a raiz (posição 1) com o elemento na posição 16 e reduzimos o heap para tamanho 15. Após heapify na raiz, o vetor fica
(9,7,8,4,6,3,8,1,2,4,5,2,1,2,5,9)

Passo 4

Passo k=15: trocamos a raiz com o elemento na posição 15, heap size = 14. Após heapify,
(8,7,8,4,6,3,5,1,2,4,5,2,1,2,9,9)

Passo 5

Passo k=14: trocamos raiz com posição 14, heap size = 13. Após heapify,
(8,7,5,4,6,3,2,1,2,4,5,2,1,8,9,9)

Passo 6

Passo k=13: trocamos raiz com posição 13, heap size = 12. Após heapify,
(7,6,5,4,5,3,2,1,2,4,1,2,8,8,9,9)

Passo 7

Passo k=12: trocamos raiz com posição 12, heap size = 11. Após heapify,
(6,5,5,4,4,3,2,1,2,2,1,7,8,8,9,9)

Passo 8

Passo k=11: trocamos raiz com posição 11, heap size = 10. Após heapify,
(5,4,5,2,4,3,2,1,1,2,6,7,8,8,9,9)

Passo 9

Passo k=10: trocamos raiz com posição 10, heap size = 9. Após heapify,
(5,4,3,2,4,2,2,1,1,5,6,7,8,8,9,9)

Passo 10

Passo k=9: trocamos raiz com posição 9, heap size = 8. Após heapify,
(4,4,3,2,1,2,2,1,5,5,6,7,8,8,9,9)

Passo 11

Passo k=8: trocamos raiz com posição 8, heap size = 7. Após heapify,
(4,2,3,1,1,2,2,4,5,5,6,7,8,8,9,9)

Passo 12

Passo k=7: trocamos raiz com posição 7, heap size = 6. Após heapify,
(3,2,2,1,1,2,4,4,5,5,6,7,8,8,9,9)

Passo 13

Passo k=6: trocamos raiz com posição 6, heap size = 5. Após heapify,
(2,2,2,1,1,3,4,4,5,5,6,7,8,8,9,9)

Passo 14

Passo k=5: trocamos raiz com posição 5, heap size = 4. Após heapify,
(2,1,2,1,2,3,4,4,5,5,6,7,8,8,9,9)

Passo 15

Passo k=4: trocamos raiz com posição 4, heap size = 3. Após heapify,
(2,1,1,2,2,3,4,4,5,5,6,7,8,8,9,9)

Passo 16

Passo k=3: trocamos raiz com posição 3, heap size = 2. Após heapify,
(1,1,2,2,2,3,4,4,5,5,6,7,8,8,9,9)

Passo 17

Passo k=2: trocamos raiz com posição 2, heap size = 1. Fim do algoritmo, o vetor já está ordenado.

Resposta

(1,1,2,2,2,3,4,4,5,5,6,7,8,8,9,9)

Exercícios relacionados