Questão de Algoritmos e Estrutura de Dados — Algoritmos — IMPARH 2024
Algoritmos e Estrutura de Dados›Algoritmos
Código
qg257246
Banca
IMPARH
Órgão
Prefeitura de Fortaleza - CE
Ano
2024
Nível
Superior
Cargo
Analista de Regulação - Ciências da Computação
Sobre algoritmos de ordenação, marque a opção correta.
AO pior caso do MergeSort ocorre quando o pivô escolhido divide mal o array, causando recursão em um lado apenas, resultando em complexidade O(n²).
BO QuickSort tem complexidade O(n log n) no melhor e médio caso, mas pode ter complexidade O(n²) no pior caso, quando o pivô divide mal o array.
CBubleSort divide o array em subarrays menores e depois os combina em ordem, aplicando a técnica de dividir para conquistar.
DO QuickSort usa mais memória que o MergeSort, pois requer memória auxiliar significativa.
Revelar gabarito e comentário▾
GabaritoB — O QuickSort tem complexidade O(n log n) no melhor e médio caso, mas pode ter complexidade O(n²) no pior caso, quando o pivô divide mal o array.
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”.
Algoritmos de Ordenação: QuickSort, MergeSort, BubbleSort
Gabarito: letra B. O QuickSort apresenta complexidade O(n log n) no melhor e médio caso, mas no pior caso (pivô mal escolhido, particionamento desbalanceado) atinge O(n²). A alternativa B descreve exatamente esse comportamento, sendo a única correta.
A questão testa o conhecimento das características fundamentais dos principais algoritmos de ordenação. A banca explora confusões comuns: troca de conceitos entre MergeSort e QuickSort, descrição incorreta do BubbleSort e inversão da memória usada.
Algoritmo
Complexidade Melhor/Médio Caso
Complexidade Pior Caso
Característica de Particionamento
Uso de Memória Extra
QuickSort
O(n log n)
O(n²)
Pivô pode dividir mal o array (desbalanceado)
O(log n) (pilha de recursão)
MergeSort
O(n log n)
O(n log n)
Divisão sempre balanceada (meio do array)
O(n) (arrays auxiliares)
BubbleSort
O(n) (melhor) / O(n²) (médio)
O(n²)
Não usa divisão; comparações e trocas adjacentes
O(1) (in-place)
Algoritmos de ordenação: QuickSort (Melhor/médio caso: O(n log n), Pior caso: O(n²) (pivô mal escolhido), In-place: O(log n) memória); MergeSort (Todos os casos: O(n log n), Memória extra: O(n)); BubbleSort (Médio/pior caso: O(n²), Comparações e trocas adjacentes)
Alternativa A — ❌ Incorreta
Afirma que o pior caso do MergeSort é O(n²) quando o pivô divide mal o array. Erro: quem usa pivô e pode ter partição desbalanceada é o QuickSort, não o MergeSort. O MergeSort sempre divide o array ao meio (divisão balanceada) e tem complexidade O(n log n) em todos os casos.
Alternativa B — ✅ Correta ⟵ GABARITO
Exato. O QuickSort tem:
Melhor caso: O(n log n) – pivô divide em partes aproximadamente iguais.
Médio caso: O(n log n) – para entradas aleatórias.
Pior caso: O(n²) – quando o pivô é sempre o menor ou maior elemento (ex.: array já ordenado e pivô fixo na extremidade), gerando partições de tamanho 1 e n-1.
Alternativa C — ❌ Incorreta
Descreve o BubbleSort como "divide o array em subarrays e combina, aplicando dividir para conquistar". Erro: Isso é característica do MergeSort ou QuickSort. O BubbleSort funciona por comparações e trocas sucessivas entre elementos adjacentes, sem divisão recursiva. Sua complexidade é O(n²) médio/pior caso.
Alternativa D — ❌ Incorreta
Afirma que o QuickSort "usa mais memória que o MergeSort, pois requer memória auxiliar significativa". Erro: é o contrário. O MergeSort requer O(n) de memória extra (arrays auxiliares para intercalação). O QuickSort é in-place: usa apenas O(log n) de espaço extra (pilha de recursão). Portanto, o MergeSort consome mais memória.
NÃO CAIA NESSA!
A banca troca propositalmente as características:
Alternativa A: atribui o pior caso O(n²) ao MergeSort, quando é do QuickSort.
Alternativa D: inverte a relação de uso de memória (QuickSort é o mais econômico).
Fique atento: ao falar em "pivô" e "divisão mal do array", pense imediatamente em QuickSort; ao falar em "divisão ao meio" e "intercalação", pense em MergeSort.