Questão de Engenharia Elétrica/Eletrônica · CEBRASPE PF 2025 (nº 107)

O conceito-chave é que o Quick Sort é um algoritmo de ordenação que divide o problema em partes menores (usando um "pivô") e ordena cada parte recursivamente. Na maioria das vezes, essa divisão é equilibrada, o que gera um custo de $O(n \log n)$; porém, se o pivô for sempre o menor ou o maior elemento (ex.: lista já ordenada), a divisão fica desequilibrada e o custo dispara para $O(n^2)$.

• Correta: Certo. A afirmação descreve exatamente o comportamento do Quick Sort: complexidade média $O(n \log n)$ e pior caso $O(n^2)$, que ocorre quando as partições são muito desiguais (ex.: pivô sempre extremo).

Fica de olho: a banca pode trocar "pior caso" por "melhor caso" ou afirmar que o pior caso é $O(n \log n)$ — o que estaria errado. Outra pegadinha comum é dizer que o Quick Sort é estável ou que seu pior caso é $O(n \log n)$ para qualquer entrada, quando na verdade a escolha do pivô (e a entrada) pode degradar o desempenho para $O(n^2)$.