Algoritmos e Estrutura de Dados · COPEVE-UFAL · 2023 | Questão sqc-qq852591

Algoritmos e Estrutura de DadosAlgoritmos

Código: qq852591
Banca: COPEVE-UFAL
Órgão: UFAL
Ano: 2023
Nível: Médio

Cargo: COPEVE - - Técnico de Tecnologia da Informação

O quicksort é um dos algoritmos mais famosos de ordenação, o qual, por sua vez, é um tema bastante estudado na informática. Mas, qual a vantagem do quicksort afinal?Assinale a alternativa que contém uma descrição correta sobre o algoritmo

AApesar de não estável, o quicksort é um algoritmo rápido, cujas operações são realizadas sem a necessidade de vetor auxiliar, o qual ainda demanda um esforço computacional baixo, cujo caso médio é O(n log n)
BMesmo sendo estável, o quicksort é um algoritmo rápido, cujas operações são realizadas sem a necessidade de vetor auxiliar, o qual ainda demanda um esforço computacional baixo, cujo caso médio é O(log n)
CMesmo sendo estável, o quicksort é um algoritmo rápido, cujas operações são realizadas com uso de vetor auxiliar, o qual ainda demanda um esforço computacional baixo, cujo caso médio é O(n log n)
DMesmo sendo estável, o quicksort é um algoritmo rápido, cujas operações são realizadas com uso de vetor auxiliar, o qual ainda demanda um esforço computacional baixo, cujo caso médio é O(log n)
EApesar de não estável, o quicksort é um algoritmo rápido, cujas operações são realizadas com uso de vetor auxiliar, o qual ainda demanda um esforço computacional baixo, cujo caso médio é O(log n).

Revelar gabarito e comentário

GabaritoA — Apesar de não estável, o quicksort é um algoritmo rápido, cujas operações são realizadas sem a necessidade de vetor auxiliar, o qual ainda demanda um esforço computacional baixo, cujo caso médio é O(n log n)

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”.

Quicksort

Gabarito: letra A. O quicksort é um algoritmo de ordenação não estável, que ordena in-place (sem necessidade de vetor auxiliar) e apresenta complexidade de caso médio O(n log n). Essas três características são corretamente descritas na alternativa A, conforme a literatura sobre o algoritmo.

A banca testa o conhecimento das propriedades fundamentais do quicksort: estabilidade, uso de memória auxiliar e complexidade assintótica. Observe que a maioria das alternativas mistura essas características de forma incorreta.

Quicksort: Estabilidade (Não estável); Memória (In-place (sem vetor auxiliar), Pilha de recursão: O(log n)); Complexidade (Caso médio: O(n log n), Pior caso: O(n²))

Alternativa A — ✅ Correta ⟵ GABARITO

Afirma que o quicksort "apesar de não estável" (correto), "sem a necessidade de vetor auxiliar" (correto, ordenação in-place) e "caso médio é O(n log n)" (correto). A descrição é integralmente verdadeira.

Alternativa B — ❌ Incorreta

Erro na estabilidade: o quicksort não é estável, a alternativa diz "mesmo sendo estável". Além disso, a complexidade média é O(n log n), não O(log n) como consta.

Alternativa C — ❌ Incorreta

Afirma que o quicksort é estável (falso) e que utiliza vetor auxiliar (falso, é in-place). A complexidade O(n log n) está correta, mas os dois erros anteriores tornam a alternativa falsa.

Alternativa D — ❌ Incorreta

Erro triplo: diz que é estável (falso), que usa vetor auxiliar (falso) e que a complexidade média é O(log n) (falso, é O(n log n)).

Alternativa E — ❌ Incorreta

Acerta na não estabilidade, mas erra ao afirmar que usa vetor auxiliar (o quicksort é in-place) e que a complexidade média é O(log n) (deveria ser O(n log n)).

PEGA ESSA DICA!

Para memorizar as características do quicksort, lembre dos três pontos: (1) não estável — a ordem relativa de elementos iguais pode mudar; (2) in-place — não requer vetor auxiliar, apenas espaço O(log n) para a pilha de recursão; (3) complexidade média O(n log n), pior caso O(n²) (raro com boas escolhas de pivô). Esses são os atributos mais cobrados em provas.

Gabarito: letra A.

Link permanente: /questoes/qq852591