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
, 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
e contar quantas trocas efetivas ocorrem, considerando que só trocamos quando o menor elemento encontrado não está já na posição
.
Passo 2
Na iteração
, buscamos o mínimo em
. O mínimo é
em índice
, igual a
, logo nenhuma troca.
swaps
swaps
Passo 3
Na iteração
, buscamos o mínimo em
. O mínimo é
em índice
, igual a
, logo nenhuma troca.
swaps
swaps
Passo 4
Na iteração
, buscamos o mínimo em
. O mínimo é
em índice
, diferente de
. Troca-se
com
:
swaps
Passo 5
Na iteração
, buscamos o mínimo em
. O mínimo é
em índice
, igual a
, logo nenhuma troca.
swaps
swaps
Passo 6
Na iteração
, buscamos o mínimo em
. O mínimo é
em índice
, diferente de
. Troca-se
com
:
swaps
Passo 7
Na iteração
, buscamos o mínimo em
. O mínimo é
em índice
, diferente de
. Troca-se
com
:
swaps