Questão de Tecnologia da Informação · FGV TRF1 2024 (nº 41)

O algoritmo de ordenação por seleção (Selection Sort) funciona encontrando repetidamente o menor elemento na parte não ordenada da lista e colocando-o na posição correta no início da parte não ordenada. A cada "iteração", um novo elemento é movido para sua posição final ordenada.

Lista inicial: [5, 3, 8, 4, 2, 7, 1, 10, 6, 9]

Detalhes das iterações para chegar à alternativa D:

• Iteração 1 (para i=0):

  • Procura o menor elemento na lista [5, 3, 8, 4, 2, 7, 1, 10, 6, 9]. O menor é 1 (na posição 6).
  • Troca 5 (posição 0) com 1 (posição 6).
  • Lista após a 1ª iteração: [1, 3, 8, 4, 2, 7, 5, 10, 6, 9] (O 1 está agora no lugar correto).

• Iteração 2 (para i=1):

  • Procura o menor elemento na parte não ordenada [3, 8, 4, 2, 7, 5, 10, 6, 9] (a partir da posição 1). O menor é 2 (na posição 4).
  • Troca 3 (posição 1) com 2 (posição 4).
  • Lista após a 2ª iteração: [1, 2, 8, 4, 3, 7, 5, 10, 6, 9] (O 2 está agora no lugar correto).

• Iteração 3 (para i=2):

  • Procura o menor elemento na parte não ordenada [8, 4, 3, 7, 5, 10, 6, 9] (a partir da posição 2). O menor é 3 (na posição 4).
  • Troca 8 (posição 2) com 3 (posição 4).
  • Lista após a 3ª iteração: [1, 2, 3, 4, 8, 7, 5, 10, 6, 9] (O 3 está agora no lugar correto).

• Iteração 4 (para i=3):

  • Procura o menor elemento na parte não ordenada [4, 8, 7, 5, 10, 6, 9] (a partir da posição 3). O menor é 4 (na posição 3).
  • Troca 4 (posição 3) com 4 (posição 3). (Não há mudança visível, mas a operação conceitual ocorre).
  • Lista após a 4ª iteração: [1, 2, 3, 4, 8, 7, 5, 10, 6, 9] (O 4 está agora no lugar correto).

• Iteração 5 (para i=4):

  • Procura o menor elemento na parte não ordenada [8, 7, 5, 10, 6, 9] (a partir da posição 4). O menor é 5 (na posição 6).
  • Troca 8 (posição 4) com 5 (posição 6).
  • Lista após a 5ª iteração: [1, 2, 3, 4, 5, 7, 8, 10, 6, 9] (O 5 está agora no lugar correto).

Apesar da questão pedir o resultado após a "terceira iteração", a alternativa correta fornecida (D) corresponde ao estado da lista após a quinta iteração do algoritmo Selection Sort, onde os cinco primeiros elementos (1, 2, 3, 4, 5) já foram corretamente posicionados. É importante estar atento a possíveis ambiguidades ou erros na numeração das iterações em questões de prova.

(A) Incorreta: Esta é a lista completamente ordenada, o que exigiria todas as 9 iterações do Selection Sort para uma lista de 10 elementos.
(B) Incorreta: Embora os três primeiros elementos (1, 2, 3) estejam corretos, a sequência dos elementos restantes (5, 4, 7, 8, 10, 6, 9) está incorreta para qualquer estágio do Selection Sort após a terceira iteração. Por exemplo, o 4 deveria estar na posição 3 (índice 3) se a iteração 4 tivesse ocorrido corretamente, ou 4 deveria ser o próximo a ser movido se estivéssemos na 4ª iteração. Esta alternativa pode ser um distrator para quem acerta as primeiras posições, mas erra a lógica de busca do mínimo ou a contagem das iterações.
(C) Incorreta: Esta alternativa mostra os cinco primeiros elementos corretamente ordenados (1, 2, 3, 4, 5), mas a sequência restante (8, 7, 10, 6, 9) não corresponde ao resultado da 5ª iteração do Selection Sort.
(D) Correta: Esta lista [1, 2, 3, 4, 5, 7, 8, 10, 6, 9] é o resultado exato após a quinta iteração do algoritmo Selection Sort, onde os cinco primeiros elementos foram corretamente colocados em suas posições finais.
(E) Incorreta: Esta alternativa também mostra os cinco primeiros elementos corretamente ordenados (1, 2, 3, 4, 5), mas a sequência restante (8, 7, 6, 9, 10) não corresponde ao resultado da 5ª iteração do Selection Sort.