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 quadrática
Gabarito: letra A. A questão pede a alternativa que contém apenas algoritmos cuja complexidade de pior caso é O(n²). Bubble sort, Insertion sort e Quicksort têm pior caso O(n²) – os dois primeiros sempre O(n²), o Quicksort no pior caso (pivô desbalanceado) também O(n²). As demais alternativas incluem algoritmos com pior caso O(n log n) (Mergesort, Heapsort), o que as exclui.
A banca testa o conhecimento das classes de complexidade dos algoritmos de ordenação. Embora o Quicksort tenha caso médio O(n log n), seu pior caso é O(n²) – e foi isso que a banca considerou. As outras alternativas misturam algoritmos quadráticos com outros de melhor desempenho.
Bubble sort (O(n²) em todos os casos), Insertion sort (O(n²) no pior/médio caso) e Quicksort (pior caso O(n²)) são todos de ordem quadrática no pior caso. Portanto, apenas algoritmos quadráticos.
Alternativa B — ❌ Incorreta
Mergesort e Heapsort têm complexidade O(n log n) no pior caso, não quadrática. Apenas Bubble sort é quadrático.
Alternativa C — ❌ Incorreta
Heapsort é O(n log n) no pior caso. Shell sort tem complexidade dependente da sequência de gaps, mas geralmente é subquadrático (O(n^(3/2)) ou O(n log² n)), não sendo puramente quadrático. Insertion sort é quadrático.
Alternativa D — ❌ Incorreta
Quicksort (caso médio O(n log n), pior O(n²) – mas não é classicamente considerado quadrático), Mergesort (O(n log n)) e Shell sort (não quadrático puro). Nenhum dos três é exclusivamente quadrático.
Alternativa E — ❌ Incorreta
Selection sort é O(n²) em todos os casos. Mergesort é O(n log n). Shell sort não é puramente quadrático.
NÃO CAIA NESSA!
O Quicksort é ambíguo: muitos alunos o lembram como O(n log n) e descartam a alternativa A. A banca, porém, usou o pior caso do Quicksort (O(n²)) para classificá-lo como quadrático. Essa é uma armadilha clássica – sempre verifique qual métrica a questão adota (pior caso, caso médio, etc.).