Pular para o conteúdo principal

Questão de Programação — Conceitos básicos de programação — Avança SP 2025

ProgramaçãoConceitos básicos de programação
Código
qg425167
Banca
Avança SP
Órgão
UNITAU
Ano
2025
Nível
Superior
Cargo
Programador Pleno
Dado um array de inteiros, implemente um algoritmo de ordenação com complexidade O(n log n) no caso médio. Qual das seguintes implementações é correta?
  1. ABubble Sort
  2. BQuick Sort
  3. CSelection Sort
  4. DInsertion Sort
  5. EMerge Sort
Revelar gabarito e comentário

GabaritoB — Quick Sort

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 e complexidade

Gabarito: letra B. O Quick Sort é o algoritmo que, no caso médio, apresenta complexidade O(n log n), sendo amplamente utilizado em implementações práticas de ordenação. As demais alternativas (Bubble Sort, Selection Sort e Insertion Sort) possuem complexidade O(n²) no caso médio, e o Merge Sort, embora também seja O(n log n), não é a resposta indicada pelo gabarito.

A complexidade de um algoritmo mede como o tempo de execução cresce em relação ao tamanho da entrada (n). No caso da ordenação, os algoritmos mais simples, como Bubble Sort, Selection Sort e Insertion Sort, percorrem o array repetidamente, resultando em O(n²) no caso médio. Já algoritmos mais eficientes, como Quick Sort e Merge Sort, utilizam a estratégia de dividir para conquistar, reduzindo a complexidade para O(n log n).

O Quick Sort funciona escolhendo um pivô e particionando o array em elementos menores e maiores que ele, recursivamente. No caso médio, essa partição equilibrada leva a O(n log n). No entanto, no pior caso (quando o pivô é sempre o menor ou o maior elemento), a complexidade degrada para O(n²). O Merge Sort, por sua vez, divide o array ao meio e intercala as metades ordenadas, garantindo O(n log n) em todos os casos, mas com custo adicional de memória.

A pegadinha desta questão está em reconhecer que o Quick Sort é o algoritmo clássico com O(n log n) no caso médio, enquanto os outros três (Bubble, Selection, Insertion) são quadráticos. O Merge Sort também é O(n log n), mas a banca considerou o Quick Sort como a resposta correta, provavelmente por ser o mais comum em implementações de bibliotecas padrão.

Guarde a tabela de complexidades: é ela que separa as alternativas.

Algoritmo

Caso médio

Pior caso

Bubble Sort

O(n²)

O(n²)

Selection Sort

O(n²)

O(n²)

Insertion Sort

O(n²)

O(n²)

Quick Sort

O(n log n)

O(n²)

Merge Sort

O(n log n)

O(n log n)

Alternativa A — ❌ Incorreta

O Bubble Sort compara elementos adjacentes e os troca até que o array esteja ordenado. Sua complexidade no caso médio é O(n²), não O(n log n). É um algoritmo simples, mas ineficiente para grandes entradas.

Alternativa B — ✅ Correta ⟵ GABARITO

O Quick Sort é o algoritmo que, no caso médio, apresenta complexidade O(n log n). Ele utiliza a técnica de dividir para conquistar, particionando o array em torno de um pivô e ordenando recursivamente as partições. É amplamente usado em implementações práticas, como na função qsort da linguagem C e em bibliotecas de Java e Python.

Alternativa C — ❌ Incorreta

O Selection Sort seleciona o menor elemento e o coloca na posição correta, repetindo o processo. Sua complexidade no caso médio é O(n²), pois realiza duas iterações aninhadas sobre o array.

Alternativa D — ❌ Incorreta

O Insertion Sort insere cada elemento na posição correta, deslocando os demais. No caso médio, sua complexidade é O(n²), embora seja eficiente para arrays quase ordenados (O(n) no melhor caso).

Alternativa E — ❌ Incorreta

O Merge Sort também possui complexidade O(n log n) no caso médio, mas não é a resposta indicada pelo gabarito. Ele divide o array ao meio e intercala as metades ordenadas, garantindo O(n log n) em todos os casos, porém com custo adicional de memória O(n). A banca considerou o Quick Sort como a implementação correta, possivelmente por ser mais comum em questões de programação.

NÃO CAIA NESSA!

A banca explora a confusão entre o caso médio e o pior caso do Quick Sort: no caso médio é O(n log n), mas no pior caso é O(n²). Além disso, o Merge Sort também é O(n log n), mas a questão pede uma implementação 'correta' — e o gabarito aponta o Quick Sort como a resposta, possivelmente por ser o mais comum em implementações práticas.

PEGA ESSA DICA!

Memorize a tabela de complexidades dos algoritmos de ordenação. Em questões que pedem O(n log n) no caso médio, as opções viáveis são Quick Sort e Merge Sort. Se a banca pedir apenas uma, verifique se há alguma menção a 'in-place' (Quick Sort) ou 'estável' (Merge Sort) para diferenciá-los.

Gabarito: letra B

Link permanente: /questoes/qg425167