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
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
até
. Depois de ajustar cada subárvore, o vetor fica
Passo 3
Passo
: 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
Passo 4
Passo
: trocamos a raiz com o elemento na posição 15, heap size = 14. Após heapify,
Passo 5
Passo
: trocamos raiz com posição 14, heap size = 13. Após heapify,
Passo 6
Passo
: trocamos raiz com posição 13, heap size = 12. Após heapify,
Passo 7
Passo
: trocamos raiz com posição 12, heap size = 11. Após heapify,
Passo 8
Passo
: trocamos raiz com posição 11, heap size = 10. Após heapify,
Passo 9
Passo
: trocamos raiz com posição 10, heap size = 9. Após heapify,
Passo 10
Passo
: trocamos raiz com posição 9, heap size = 8. Após heapify,
Passo 11
Passo
: trocamos raiz com posição 8, heap size = 7. Após heapify,
Passo 12
Passo
: trocamos raiz com posição 7, heap size = 6. Após heapify,
Passo 13
Passo
: trocamos raiz com posição 6, heap size = 5. Após heapify,
Passo 14
Passo
: trocamos raiz com posição 5, heap size = 4. Após heapify,
Passo 15
Passo
: trocamos raiz com posição 4, heap size = 3. Após heapify,
Passo 16
Passo
: trocamos raiz com posição 3, heap size = 2. Após heapify,
Passo 17
Passo
: trocamos raiz com posição 2, heap size = 1. Fim do algoritmo, o vetor já está ordenado.