Questão de Programação — Conceitos básicos de programação — Avança SP 2025
- Código
- qg425167
- Banca
- Avança SP
- Órgão
- UNITAU
- Ano
- 2025
- Nível
- Superior
- Cargo
- Programador Pleno
- ABubble Sort
- BQuick Sort
- CSelection Sort
- DInsertion Sort
- EMerge Sort
GabaritoB — Quick Sort
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) |
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.
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.
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.
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).
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.
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.
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