Selection Sort: simulação passo a passo
Gabarito: letra D. A terceira saída intermediária é ALAÍDE - BRUNA - CARLA | ÉLCIO - DANIEL - FÁBIO. O Selection Sort, a cada iteração, encontra o menor elemento da parte ainda não ordenada e o troca com o primeiro elemento dessa parte; na terceira iteração, o menor entre {DANIEL, ÉLCIO, CARLA, FÁBIO} é CARLA, que troca de posição com DANIEL.
O Selection Sort é um algoritmo de ordenação que funciona em passos. Em cada passo, ele olha para a parte da lista que ainda não foi ordenada (a partir de uma posição inicial que avança a cada iteração) e identifica o menor elemento dessa parte. Se esse menor elemento já estiver na primeira posição da parte não ordenada, nada é feito; caso contrário, ele é trocado com o elemento que está nessa primeira posição. Esse processo se repete até que toda a lista esteja ordenada.
Vamos aplicar isso à lista original: DANIEL - BRUNA - ALAÍDE - ÉLCIO - CARLA - FÁBIO.
1ª iteração: A parte não ordenada é a lista inteira. O menor elemento é ALAÍDE. Ele não está na primeira posição (quem está é DANIEL), então trocamos ALAÍDE com DANIEL. Resultado: ALAÍDE | BRUNA - DANIEL - ÉLCIO - CARLA - FÁBIO (a barra indica a fronteira entre a parte ordenada e a não ordenada).
2ª iteração: A parte não ordenada agora começa em BRUNA: BRUNA - DANIEL - ÉLCIO - CARLA - FÁBIO. O menor elemento é BRUNA, que já está na primeira posição dessa parte. Portanto, nenhuma troca é feita. Resultado: ALAÍDE - BRUNA | DANIEL - ÉLCIO - CARLA - FÁBIO.
3ª iteração: A parte não ordenada agora começa em DANIEL: DANIEL - ÉLCIO - CARLA - FÁBIO. O menor elemento é CARLA. Ela não está na primeira posição (quem está é DANIEL), então trocamos CARLA com DANIEL. Resultado: ALAÍDE - BRUNA - CARLA | ÉLCIO - DANIEL - FÁBIO.
A pegadinha desta questão está em não confundir o Selection Sort com outros algoritmos, como o Bubble Sort (que compara elementos adjacentes e os troca repetidamente) ou o Insertion Sort (que insere cada elemento em sua posição correta na parte já ordenada). No Selection Sort, a cada iteração apenas uma troca é feita (ou nenhuma, se o menor já estiver no lugar), e o menor elemento da parte não ordenada é sempre colocado na posição correta.
Guarde a essência: a cada passo, o Selection Sort seleciona o menor elemento da parte não ordenada e o coloca na primeira posição dessa parte. É exatamente essa lógica que vamos aplicar para julgar cada alternativa.
Alternativa A — ❌ Incorreta
A sequência FÁBIO - ÉLCIO - DANIEL na parte não ordenada está errada. Após a terceira iteração, a parte não ordenada é ÉLCIO - DANIEL - FÁBIO. A alternativa coloca FÁBIO antes de ÉLCIO e DANIEL, o que não corresponde ao resultado da troca entre CARLA e DANIEL.
Alternativa B — ❌ Incorreta
A sequência ÉLCIO - FÁBIO - DANIEL está errada. Após a troca entre CARLA e DANIEL, a parte não ordenada fica ÉLCIO - DANIEL - FÁBIO. A alternativa coloca FÁBIO antes de DANIEL, o que não reflete a ordem correta após a terceira iteração.
Alternativa C — ❌ Incorreta
A sequência DANIEL - ÉLCIO - FÁBIO está errada. Essa seria a parte não ordenada antes da terceira iteração, não depois. Após a troca entre CARLA e DANIEL, DANIEL não pode permanecer na primeira posição da parte não ordenada.
Alternativa D — ✅ Correta ⟵ GABARITO
A sequência ÉLCIO - DANIEL - FÁBIO está correta. Na terceira iteração, o menor elemento da parte não ordenada {DANIEL, ÉLCIO, CARLA, FÁBIO} é CARLA, que troca de posição com DANIEL. Assim, a parte não ordenada passa a ser ÉLCIO - DANIEL - FÁBIO, exatamente como a alternativa apresenta.
Alternativa E — ❌ Incorreta
A sequência DANIEL - FÁBIO - ÉLCIO está errada. Após a troca entre CARLA e DANIEL, DANIEL não pode estar na primeira posição da parte não ordenada, pois ele foi trocado com CARLA. A ordem correta é ÉLCIO - DANIEL - FÁBIO.
Gabarito: letra D