(4) Apresente o funcionamento dos métodos de ordenação por seleção e por inserção para ordenar as chaves a seguir:
3
4
9
2
5
1
8
Desenhe o vetor várias vezes demonstrando os passos de cada algoritmo. Coloque um círculo nos elementos movimentados e um traço entre os elementos ordenados e desordenados.
3 | 4 | 9 | 2 | 5 | 1 | 8 |
Passo 1
Beleza, o exercício quer que a gente mostre passo a passo como funciona o selection sort (ordenar por seleção) e o insertion sort (ordenar por inserção) para o vetor inicial
O conteúdo é Algoritmos de Ordenação. A gente vai precisar entender:
- No selection sort, a cada iteração a gente escolhe o menor elemento do pedaço não ordenado e troca com o primeiro desse pedaço.
- No insertion sort, a cada iteração a gente “insere” o próximo elemento na posição certa dentro do bloco já ordenado, deslocando os maiores.
A partir do próximo passo, mão na massa!
Passo 2
Método de Seleção (Selection Sort)
Explicação rápida: em cada passo, marcamos uma fronteira entre a parte já ordenada (à esquerda) e a não ordenada (à direita). Procuramos o menor na parte não ordenada e trocamos com o primeiro elemento não ordenado. Vamos usar para indicar os elementos que estão sendo trocados e um “
” para separar ordenado de não ordenado.
Explicação rápida: em cada passo, marcamos uma fronteira entre a parte já ordenada (à esquerda) e a não ordenada (à direita). Procuramos o menor na parte não ordenada e trocamos com o primeiro elemento não ordenado. Vamos usar
Iteração 1:
Procuramos o mínimo em , que é 1. Trocamos 1 com o primeiro elemento (3):
Procuramos o mínimo em
Iteração 2:
Agora o bloco não ordenado é . O mínimo é 2, trocamos com o primeiro desse bloco (4):
Agora o bloco não ordenado é
Iteração 3:
Bloco não ordenado . Mínimo é 3, trocamos com 9:
Bloco não ordenado
Iteração 4:
Bloco não ordenado . Mínimo é 4, já está na primeira posição desse bloco, então nada muda:
Bloco não ordenado
Iteração 5:
Bloco não ordenado . Mínimo é 5, também já está em primeiro, fica igual:
Bloco não ordenado
Iteração 6:
Bloco não ordenado . Mínimo é 8, trocamos com 9:
Bloco não ordenado
Fim do selection sort:
Passo 3
Método de Inserção (Insertion Sort)
Explicação rápida: consideramos que o primeiro elemento já forma um bloco ordenado. A cada passo, pegamos o próximo elemento e “o inserimos” no lugar certo do bloco ordenado, deslocando para a direita todos os maiores.
Explicação rápida: consideramos que o primeiro elemento já forma um bloco ordenado. A cada passo, pegamos o próximo elemento e “o inserimos” no lugar certo do bloco ordenado, deslocando para a direita todos os maiores.
Vetor inicial:
Iteração 1 (inserir 4):
4 já é ≥ 3, então só aumenta o bloco ordenado:
4 já é ≥ 3, então só aumenta o bloco ordenado:
Iteração 2 (inserir 9):
9 ≥ 4, nada muda:
9 ≥ 4, nada muda:
Iteração 3 (inserir 2):
Comparamos 2 com 9,4,3. Todos são maiores, então deslocamos:
Comparamos 2 com 9,4,3. Todos são maiores, então deslocamos:
e inserimos 2:
Iteração 4 (inserir 5):
Comparamos 5 com 9 (maior) e deslocamos, depois 5 ≥ 4, então para:
Comparamos 5 com 9 (maior) e deslocamos, depois 5 ≥ 4, então para:
Iteração 5 (inserir 1):
1 < tudo, então desloca tudo até começar e insere:
1 < tudo, então desloca tudo até começar e insere:
Iteração 6 (inserir 8):
8 < 5? Não, 8 < nada mais, só desloca 9:
8 < 5? Não, 8 < nada mais, só desloca 9:
Fim do insertion sort:
Resposta
Após executar passo a passo os dois algoritmos, chegamos ao vetor ordenado