Questão de Algoritmos e Estrutura de Dados — Algoritmos — COSEAC 2025

Algoritmos de Ordenação: Selection Sort

Gabarito: letra C. O método descrito no enunciado — percorrer o vetor a cada iteração, descobrir o menor elemento e colocá-lo em sua posição definitiva — é a definição clássica da ordenação por seleção (selection sort). Esse algoritmo divide o vetor em duas partes: a ordenada (à esquerda) e a não ordenada (à direita). A cada passo, busca-se o menor elemento na parte não ordenada e troca-se com o primeiro elemento dessa parte, consolidando-o na posição correta.

Alternativa A — ❌ Incorreta

O shell sort é uma generalização do insertion sort que permite trocas entre elementos distantes, reduzindo o problema a inserções em intervalos menores. Não há a ideia de selecionar o menor elemento a cada iteração.

Alternativa B — ❌ Incorreta

O bubble sort percorre o vetor comparando pares adjacentes e realizando trocas para "flutuar" os maiores elementos para o final. A cada iteração, o maior elemento vai para sua posição, não o menor (a menos que invertido). A descrição do enunciado fala em descobrir o menor elemento e colocá-lo na posição definitiva, o que não é característico do bubble sort.

Alternativa C — ✅ Correta ⟵ GABARITO

A ordenação por seleção direta (selection sort) executa exatamente o que foi descrito: a cada iteração encontra o menor elemento da parte não ordenada e o move para o início (posição definitiva). É um algoritmo simples, O(n²) no pior caso, mas que realiza poucas trocas (no máximo n-1).

Alternativa D — ❌ Incorreta

O quicksort utiliza um pivô e particiona o vetor em elementos menores e maiores que ele, ordenando recursivamente as partições. Não há a ideia de selecionar o menor elemento a cada iteração de forma sequencial.

Alternativa E — ❌ Incorreta

A ordenação por inserção (insertion sort) constrói a sequência ordenada inserindo cada elemento na posição correta entre os já ordenados, como se organiza cartas de baralho. Não há busca explícita do menor elemento.

Gabarito: letra C.