Questão de Algoritmos e Estrutura de Dados — Algoritmos — IF Sul Rio-Grandense 2025

Algoritmos de Ordenação

Gabarito: letra D — estão corretas apenas as afirmativas II, III e IV. O bubble sort (I) é ineficiente para grandes conjuntos de dados, enquanto insertion sort, quick sort e selection sort têm as características descritas nas demais afirmativas.

A questão cobra o conhecimento básico sobre as características e eficiência dos principais algoritmos de ordenação. Vamos analisar cada item.

Item I — ❌ Incorreto

"Bubble sort é um algoritmo de ordenação simples e muito eficiente para grande conjunto de dados." A afirmação é falsa: embora o bubble sort seja simples, ele possui complexidade $O(n^2)$ no pior caso e no caso médio, tornando-se inviável para grandes conjuntos de dados. Algoritmos como quicksort, mergesort ou heapsort são mais adequados para grandes volumes.

Item II — ✅ Correto

"Insertion sort é um algoritmo de ordenação utilizado para um pequeno número de elementos." Correto. O insertion sort tem complexidade $O(n^2)$ no pior caso, mas é eficiente para listas pequenas ou quase ordenadas (melhor caso $O(n)$). É comumente usado em conjunto com outros algoritmos para pequenas sublistas.

Item III — ✅ Correto

"Quick sort é um algoritmo de ordenação mais rápido, que emprega a técnica de divisão e conquista." Correto. O quicksort é um algoritmo de divisão e conquista, com complexidade média $O(n \log n)$ e geralmente é o mais rápido na prática para a maioria das entradas.

Item IV — ✅ Correto

"Selection sort recebe esse nome pela maneira como ele percorre o array ao longo das iterações: ele seleciona o menor elemento atual e o troca de lugar." Correto. No selection sort, a cada iteração encontra-se o menor elemento do subarray não ordenado e o troca com o primeiro elemento desse subarray. O nome deriva exatamente dessa seleção.

Conclusão: corretos os itens II, III e IV. Portanto, a alternativa D é o gabarito.