Algoritmos e Estrutura de Dados · IDECAN · 2025 | Questão sqc-qg523035

Algoritmos de ordenação: pior caso com dados ordenados

Gabarito: letra B. O Quicksort com pivô fixo na primeira posição (ou no último elemento) apresenta, no pior caso, complexidade $O(n^2)$ quando a entrada já está ordenada. Isso ocorre porque as partições ficam extremamente desbalanceadas: uma sublista vazia e outra com $n-1$ elementos, gerando o maior número possível de comparações e divisões desbalanceadas. Nenhum dos outros algoritmos listados sofre dessa patologia na mesma entrada.

A questão testa o conhecimento sobre o comportamento assintótico dos algoritmos de ordenação no pior caso, especialmente quando a entrada é ordenada. O pivô fixo no Quicksort clássico é o gatilho para o pior desempenho.

Algoritmo	Pior caso com dados ordenados	Complexidade no pior caso	Causa do desempenho
Shellsort (Hibbard)	Não sofre degradação específica	O(n³⁄²)	Sequência de incrementos evita partições desbalanceadas
Quicksort (pivô fixo na 1ª posição)	Sofre degradação máxima	O(n²)	Partições desbalanceadas: subvetor vazio e outro com n−1 elementos
Mergesort	Não sofre degradação	Θ(n log n)	Divisão sempre ao meio, independente da ordem
Heapsort	Não sofre degradação	O(n log n)	Construção e remoção do heap independentes da ordenação
Quicksort (pivô aleatório)	Evita na prática (probabilidade baixíssima)	O(n²) (teórico)	Aleatoriedade tende a partições balanceadas

Quicksort com pivô fixo

1Pior caso: dados ordenados
- Partição desbalanceada
  - Uma sublista vazia
  - Outra com n-1 elementos
- Complexidade O(n²)
2Causa
- Pivô na primeira posição
- Entrada crescente ou decrescente

LEVEL · soulevel.com.br

Alternativa A — ❌ Incorreta

O Shellsort com sequência de incrementos de Hibbard tem complexidade $O(n^{3/2})$ no pior caso, que é melhor que $O(n^2)$ . Além disso, não há o problema de divisões desbalanceadas como no Quicksort com pivô fixo.

Alternativa B — ✅ Correta ⟵ GABARITO

O Quicksort com pivô fixo na primeira posição, quando os dados já estão ordenados (crescente ou decrescente), realiza partições em que um dos subvetores fica vazio e o outro contém todos os elementos restantes. Isso gera $n$ níveis de recursão, cada um realizando $O(n)$ comparações, totalizando $O(n^2)$ comparações. É o pior caso possível para esse algoritmo.

Alternativa C — ❌ Incorreta

O Mergesort sempre divide o vetor ao meio recursivamente, independentemente da ordem dos dados. A complexidade é $\Theta(n \log n)$ no pior caso, e as divisões são balanceadas. Não há piora significativa com a entrada ordenada.

Alternativa D — ❌ Incorreta

O Heapsort também possui complexidade $O(n \log n)$ no pior caso, pois a construção do heap e as remoções sucessivas são realizadas de forma eficiente. A ordenação dos dados não altera a profundidade do heap nem o número de comparações assintoticamente.

Alternativa E — ❌ Incorreta

O Quicksort com escolha aleatória de pivô evita o pior caso na prática, pois a aleatoriedade tende a produzir partições razoavelmente balanceadas. Embora teoricamente o pior caso ainda seja $O(n^2)$ (com probabilidade baixíssima), o cenário específico de dados ordenados com pivô aleatório não causa o mesmo desbalanceamento extremo que o pivô fixo. A banca considera que o pior caso do Quicksort aleatorizado não é tão grave quanto o do Quicksort determinístico com pivô fixo, especialmente para a entrada citada.

NÃO CAIA NESSA!

Alunos podem confundir o Quicksort aleatorizado com o determinístico. A chave é que a escolha fixa do primeiro elemento (sem aleatoriedade) é a causa do colapso para $O(n^2)$ . O Quicksort aleatorizado, mesmo no pior caso teórico, não é ativado pela simples ordenação crescente, pois a escolha do pivô é aleatória. Portanto, a alternativa E está incorreta.

Gabarito: letra B.