Questão de Arquitetura de Software — Software — Fundação FAPEC 2021
Arquitetura de Software›Software
Código
qq634572
Banca
Fundação FAPEC
Órgão
PC-MS
Ano
2021
Nível
Superior
Cargo
FAPEC - - Perito Criminal - Área 01 (Análise de Sistemas, Engenharia da Computação e Ciências da Computação)
Algoritmos de ordenação por comparação são aqueles em que a ordem dos elementos na solução é determinada exclusivamente por meio da comparação entre elementos da entrada. Tais algoritmos são necessários quando não se sabe nenhuma outra informação sobre a entrada (como por exemplo, o maior elemento ou a quantidade de bits de cada elemento), além da ordem relativa entre os elementos. Para uma entrada, nessas condições com elementos, assinale a alternativa correta.
AExiste apenas um algoritmo conhecido que pode ordenar esses elementos em tempo no pior caso.
BA implementação padrão do algoritmo Ordenação por Separação, ou Quick Sort, ordenará este conjunto em tempo no pior caso.
CNo melhor caso, o algoritmo Ordenação por Inserção, ou Insertion Sort, termina em tempo .
DQualquer algoritmo de ordenação por comparação deverá realizar comparações no pior caso.
EAlgoritmos de ordenação por comparação podem ordenar os elementos apenas se eles forem números inteiros ou reais.
Revelar gabarito e comentário▾
GabaritoD — Qualquer algoritmo de ordenação por comparação deverá realizar comparações no pior caso.
Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.
Análise das Alternativas sobre Algoritmos de Ordenação por Comparação
Gabarito: letra D. A alternativa D está correta porque todo algoritmo de ordenação por comparação, por definição, baseia-se exclusivamente em comparações entre elementos para determinar a ordem. Assim, no pior caso, ele necessariamente realiza comparações – aliás, o limite inferior teórico é de Ω(n log n) comparações, conforme demonstrado na literatura (e.g., Cormen et al., Introduction to Algorithms). As demais alternativas apresentam afirmações falsas ou incompletas.
Alternativa A — ❌ Incorreta
Afirma que existe apenas um algoritmo conhecido que pode ordenar em tempo O(n log n) no pior caso. Isso é falso. Vários algoritmos, como Merge Sort e Heap Sort, garantem O(n log n) no pior caso. Não há um único algoritmo, mas sim uma família de algoritmos com essa propriedade.
Alternativa B — ❌ Incorreta
A implementação padrão do Quick Sort (que escolhe o primeiro ou o último elemento como pivô) tem pior caso O(n²), não O(n log n). Embora existam variações (como Quick Sort aleatorizado) que atingem O(n log n) esperado, a afirmação sobre a implementação padrão está errada.
Alternativa C — ❌ Incorreta
A alternativa está incompleta e, mesmo que fosse "O(n)", não é uma afirmação geral sobre o pior caso. O melhor caso do Insertion Sort é O(n) quando a entrada já está ordenada, mas a questão trata do pior caso e de um contexto genérico. Além disso, a redação truncada invalida a alternativa.
Alternativa D — ✅ Correta ⟵ GABARITO
Correta. Qualquer algoritmo de ordenação por comparação, para uma entrada de tamanho n, deve realizar um número mínimo de comparações no pior caso. Esse número é da ordem de O(n log n) (limite inferior), mas o que importa é que ele deve realizar comparações – não é possível ordenar sem comparar. A afirmação é verdadeira e se alinha com a definição do problema.
Alternativa E — ❌ Incorreta
Algoritmos de ordenação por comparação podem ordenar qualquer conjunto de dados que possua uma relação de ordem total, independentemente do tipo: strings, objetos, etc. Não se limitam a números inteiros ou reais.
PEGA ESSA DICA!
Lembre-se do teorema do limite inferior para algoritmos de ordenação por comparação: qualquer algoritmo determinístico nessa classe requer Ω(n log n) comparações no pior caso. Esse resultado é clássico e frequentemente cobrado em concursos. Para fixar, compare com o fato de que algoritmos como Counting Sort ou Radix Sort (que não são baseados em comparação) podem superar esse limite, mas exigem conhecimento adicional sobre a entrada.