Considere o algoritmo do selection sort, cujo loop interno faz a seleção do menor elemento. Depois que o elemento é selecionado, ele é trazido para sua posição definitiva em apenas uma troca. Considerando a entrada A=[1,2,4,3,7,5,6], quantas trocas seriam feitas pelo algoritmo do selection sort aplicado a essa entrada?

Passo 1

O enunciado nos pede para aplicar o selection sort em [1,2,4,3,7,5,6] e contar quantas trocas efetivas ocorrem, considerando que só trocamos quando o menor elemento encontrado não está já na posição i.

Passo 2

Na iteração i=0, buscamos o mínimo em [1,2,4,3,7,5,6]. O mínimo é 1 em índice 0, igual a i, logo nenhuma troca.
swaps =0

Passo 3

Na iteração i=1, buscamos o mínimo em [2,4,3,7,5,6]. O mínimo é 2 em índice 1, igual a i, logo nenhuma troca.
swaps =0

Passo 4

Na iteração i=2, buscamos o mínimo em [4,3,7,5,6]. O mínimo é 3 em índice 3, diferente de i. Troca-se 4 com 3:
[1,2,4,3,7,5,6]\;\longrightarrow\;[1,2,3,4,7,5,6]
swaps =1

Passo 5

Na iteração i=3, buscamos o mínimo em [4,7,5,6]. O mínimo é 4 em índice 3, igual a i, logo nenhuma troca.
swaps =1

Passo 6

Na iteração i=4, buscamos o mínimo em [7,5,6]. O mínimo é 5 em índice 5, diferente de i. Troca-se 7 com 5:
[1,2,3,4,7,5,6]\;\longrightarrow\;[1,2,3,4,5,7,6]
swaps =2

Passo 7

Na iteração i=5, buscamos o mínimo em [7,6]. O mínimo é 6 em índice 6, diferente de i. Troca-se 7 com 6:
[1,2,3,4,5,7,6]\;\longrightarrow\;[1,2,3,4,5,6,7]
swaps =3

Resposta

3 trocas.

Exercícios relacionados