Algoritmos e Estrutura de Dados · FGV · 2021 | Questão sqc-fg046245

Algoritmos de Ordenação: Identificação pelo Traçado

Gabarito: letra A. O algoritmo descrito é o Bubble Sort. A cada iteração, o maior elemento é "empurrado" para o final do array, como mostrado na sequência: após o primeiro ciclo, o 16 vai para o último lugar; após o segundo, o 14 fica na penúltima posição; e assim sucessivamente. Esse comportamento é típico do Bubble Sort, que compara pares adjacentes e realiza trocas, percorrendo o array repetidamente.

A banca testa a capacidade de reconhecer algoritmos de ordenação pelo rastro deixado a cada passagem. No Bubble Sort, após cada iteração completa, o maior elemento se fixa na posição correta, reduzindo o intervalo de comparação.

Algoritmo	Característica principal	Comportamento observado na sequência	Ordenação in place
Bubble Sort	Compara pares adjacentes e "empurra" o maior elemento para o final a cada iteração.	O maior elemento (16) vai para o final no primeiro ciclo; o segundo maior (14) vai para a penúltima posição no segundo ciclo; e assim sucessivamente.	Sim
Insertion Sort	Constrói a ordenação inserindo cada novo elemento na posição correta da parte já ordenada (à esquerda).	A parte inicial do array ficaria ordenada progressivamente, o que não é observado na sequência.	Sim
QuickSort	Escolhe um pivô e particiona o array em subconjuntos menores e maiores que o pivô.	A sequência não mostra partições nem efeito de pivô; mostra deslocamento gradual do maior elemento.	Sim
Selection Sort	Seleciona o menor elemento restante e o coloca no início do array.	O menor elemento (4) só vai para o início no último ciclo; o comportamento é oposto ao observado.	Sim
Shellsort	Ordena elementos distantes entre si, reduzindo gradualmente o intervalo de comparação.	A sequência não mostra ordenação por intervalos decrescentes; mostra deslocamento gradual do maior elemento.	Sim

1Compara pares adjacentes
2Troca se fora de ordem
3Maior elemento borbulha ao fim
4Repete intervalo reduzido
5Array ordenado

LEVEL · soulevel.com.br

Alternativa A — ✅ Correta ⟵ GABARITO

A sequência apresentada segue exatamente o padrão do Bubble Sort: a cada iteração, o maior elemento "borbulha" até o fim. Por exemplo, na primeira passagem, o 16 chegou ao final; na segunda, o 14 ficou na penúltima posição; e assim por diante, até o array estar totalmente ordenado. O algoritmo é in place e não usa memória auxiliar.

Alternativa B — ❌ Incorreta

O Insertion Sort constrói a ordenação progressivamente inserindo cada novo elemento na posição correta da parte já ordenada, normalmente à esquerda. O traçado dado (o maior sempre indo para o final) não corresponde ao comportamento típico do Insertion Sort, que manteria uma parte inicial ordenada e iria inserindo os demais.

Alternativa C — ❌ Incorreta

O QuickSort é recursivo e baseia-se na escolha de um pivô, particionando o array em subconjuntos. As sequências parciais não mostram partições nem efeito de pivô; em vez disso, mostram um deslocamento gradual do maior elemento para a direita, incompatível com o QuickSort.

Alternativa D — ❌ Incorreta

O Selection Sort seleciona a cada iteração o menor elemento restante e o coloca no início do array. Na sequência fornecida, o que ocorre é o oposto: o maior elemento vai para o final a cada ciclo, caracterizando o Bubble Sort. A confusão com Selection Sort é uma pegadinha comum, mas aqui os elementos são posicionados do maior para o menor, e não do menor para o maior.

Alternativa E — ❌ Incorreta

O Shellsort é uma generalização do Insertion Sort que compara e troca elementos distantes, reduzindo gradualmente o intervalo (gap). O padrão apresentado (cada passagem colocando o maior no final) é típico do Bubble Sort, não do Shellsort.

NÃO CAIA NESSA!

A banca pode induzir o candidato a confundir Bubble Sort com Selection Sort. Lembre-se: no Bubble Sort, a cada iteração o maior elemento vai para o final; no Selection Sort, o menor elemento vai para o início. Aqui, a sequência mostra claramente o maior (16, depois 14, etc.) sendo deslocado para a direita, o que é Bubble Sort.

Gabarito: letra A (Bubble Sort).