(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.

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
[3,,4,,9,,2,,5,,1,,8]
O conteúdo é Algoritmos de Ordenação. A gente vai precisar entender:
  1. 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.
  2. 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 [mathring1,,4,,9,,2,,5,,mathring3,,8] ;longrightarrow; [1 ;mid; 4,,9,,2,,5,,3,,8] para indicar os elementos que estão sendo trocados e um “ [1,,mathring2,,9,,mathring4,,5,,3,,8] ;longrightarrow; [1,,2 ;mid; 9,,4,,5,,3,,8] ” para separar ordenado de não ordenado.
Iteração 1:
Procuramos o mínimo em [1,,2,,mathring3,,4,,5,,mathring9,,8] ;longrightarrow; [1,,2,,3 ;mid; 4,,5,,9,,8] , que é 1. Trocamos 1 com o primeiro elemento (3):
[1,2,3,,4 ;mid; 5,9,8]
Iteração 2:
Agora o bloco não ordenado é [1,2,3,4,,5 ;mid; 9,8] . O mínimo é 2, trocamos com o primeiro desse bloco (4):
[1,2,3,4,5,,mathring8,,mathring9] ;longrightarrow; [1,2,3,4,5,8 ;mid; 9]
Iteração 3:
Bloco não ordenado [1,,2,,3,,4,,5,,8,,9] . Mínimo é 3, trocamos com 9:
Iteração 4:
Bloco não ordenado . Mínimo é 4, já está na primeira posição desse bloco, então nada muda:
Iteração 5:
Bloco não ordenado . Mínimo é 5, também já está em primeiro, fica igual:
Iteração 6:
Bloco não ordenado . Mínimo é 8, trocamos com 9:
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.
Vetor inicial:
[3 ;mid; 4,,9,,2,,5,,1,,8]
Iteração 1 (inserir 4):
4 já é ≥ 3, então só aumenta o bloco ordenado:
[3,,4 ;mid; 9,,2,,5,,1,,8]
Iteração 2 (inserir 9):
9 ≥ 4, nada muda:
[3,,4,,9 ;mid; 2,,5,,1,,8]
Iteração 3 (inserir 2):
Comparamos 2 com 9,4,3. Todos são maiores, então deslocamos:
[3,,4,,mathring9,,mathring9,,2,dots]to [3,,mathring4,,mathring4,,9,dots]to [mathring3,,mathring3,,4,9,dots]
e inserimos 2:
[2,,3,,4,,9 ;mid; 5,,1,,8]
Iteração 4 (inserir 5):
Comparamos 5 com 9 (maior) e deslocamos, depois 5 ≥ 4, então para:
[2,3,4,,mathring9,,dots]to [2,3,,mathring5,,9,dots]to [2,3,4,5 ;mid; 1,8]
Iteração 5 (inserir 1):
1 < tudo, então desloca tudo até começar e insere:
[mathring2,mathring2,mathring3,mathring4,mathring5,,1,,8]to [1,,2,3,4,5 ;mid; 8]
Iteração 6 (inserir 8):
8 < 5? Não, 8 < nada mais, só desloca 9:
[1,2,3,4,5,,mathring9,dots]to [1,2,3,4,5,8,9]
Fim do insertion sort:
[1,,2,,3,,4,,5,,8,,9]

Resposta

Após executar passo a passo os dois algoritmos, chegamos ao vetor ordenado
[1,,2,,3,,4,,5,,8,,9]

Exercícios relacionados