Questão de Algoritmos e Estrutura de Dados — Algoritmos — IV - UFG 2024
Algoritmos e Estrutura de Dados›Algoritmos
Código
qg121569
Banca
IV - UFG
Órgão
TJ-AC
Ano
2024
Nível
Superior
Cargo
CS-UFG - - Analista Judiciário - Analista de Sistemas
Medir a complexidade dos métodos de ordenação é fundamental para entender o desempenho desses algoritmos e poder fazer escolhas adequadas dependendo do contexto do problema. Qual método de ordenação o pior caso tem a mesma complexidade do método Quick Sort no pior caso?
AHeap Sort.
BBuble Sort.
CMerge Sort.
DRadix Sort.
Revelar gabarito e comentário▾
GabaritoB — Buble Sort.
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”.
Complexidade de algoritmos de ordenação
Gabarito: letra B. O pior caso do Quick Sort é O(n²), mesma complexidade do Bubble Sort (também O(n²) no pior caso). Heap Sort e Merge Sort têm pior caso O(n log n), e Radix Sort tem complexidade distinta (O(kn)), não se igualando a O(n²).
A questão testa o conhecimento das complexidades dos principais algoritmos de ordenação, especialmente o comportamento no pior cenário. O Quick Sort, quando o pivô é sempre o menor ou maior elemento (lista já ordenada, por exemplo), atinge O(n²). A mesma complexidade ocorre no Bubble Sort quando o vetor está em ordem inversa. Os demais algoritmos apresentam garantias melhores ou estruturas diferentes.
Heap Sort possui complexidade O(n log n) tanto no pior, melhor quanto no caso médio. Nunca atinge O(n²).
Alternativa B — ✅ Correta ⟵ GABARITO
Bubble Sort tem pior caso O(n²), exatamente como o Quick Sort. Ocorre quando o vetor está ordenado inversamente, exigindo n(n-1)/2 comparações e trocas.
Alternativa C — ❌ Incorreta
Merge Sort sempre executa em O(n log n) no pior caso, independentemente da entrada. É um algoritmo estável e de divisão e conquista.
Alternativa D — ❌ Incorreta
Radix Sort é um algoritmo de ordenação não comparativo. Sua complexidade é O(d \cdot (n + k)), onde d é o número de dígitos e k é a base. Não se enquadra na classe O(n²).