Questão de Algoritmos e Estrutura de Dados — Algoritmos — COPESE - UFPI 2024
Algoritmos e Estrutura de Dados›Algoritmos
Código
qg107650
Banca
COPESE - UFPI
Órgão
UFPI
Ano
2024
Nível
Médio
Cargo
COPESE - - Técnico de Tecnologia da Informação
Assinale a opção que descreve CORRETAMENTE o algoritmo de ordenação Quicksort aplicado a um array:
AQuicksort é um algoritmo de ordenação que utiliza a técnica de dividir e conquistar, selecionando um pivô e particionando o array em sub-arrays menores e maiores que o pivô.
BQuicksort é um algoritmo de ordenação estável que mantém a ordem relativa dos elementos iguais.
CQuicksort tem um pior caso de complexidade de tempo O (n^2) e é sempre mais lento que o algoritmo Bubble Sort.
DQuicksort é um algoritmo de ordenação que requer espaço adicional proporcional ao tamanho do array.
EQuicksort é um algoritmo de ordenação que sempre seleciona o primeiro elemento como pivô.
Revelar gabarito e comentário▾
GabaritoA — Quicksort é um algoritmo de ordenação que utiliza a técnica de dividir e conquistar, selecionando um pivô e particionando o array em sub-arrays menores e maiores que o pivô.
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”.
Quicksort — Descrição Correta
Gabarito: letra A. O Quicksort é um algoritmo de ordenação que utiliza a estratégia de dividir e conquistar, escolhendo um pivô e particionando o array em elementos menores e maiores que ele. As demais alternativas contêm erros conceituais sobre estabilidade, complexidade e escolha do pivô.
O texto de apoio (fonte clássica) define o Quicksort como um algoritmo de ordenação por comparação não estável, que adota a estratégia de divisão e conquista: seleciona um pivô, rearranja a lista de modo que os elementos menores fiquem antes e os maiores depois, e recursivamente ordena as duas sublistas.
Alternativa A — ✅ Correta ⟵ GABARITO
Descreve exatamente o funcionamento do Quicksort: técnica de dividir e conquistar, seleção de um pivô e particionamento do array em sub‑arrays menores e maiores que o pivô. É a definição fundamental do algoritmo.
Alternativa B — ❌ Incorreta
Afirma que o Quicksort é estável. O Quicksort não é estável, pois não preserva necessariamente a ordem relativa dos elementos iguais. A estabilidade é uma propriedade de algoritmos como o Mergesort ou o Insertion Sort, não do Quicksort.
Alternativa C — ❌ Incorreta
Diz que o Quicksort tem pior caso O(n²) e que é sempre mais lento que o Bubble Sort. Embora ambos tenham pior caso O(n²), o Quicksort é, na prática, muito mais rápido que o Bubble Sort na maioria dos casos; a afirmação "sempre mais lento" é uma generalização falsa. Além disso, o Bubble Sort também tem pior caso O(n²), mas desempenho inferior em média.
Alternativa D — ❌ Incorreta
Declara que o Quicksort requer espaço adicional proporcional ao tamanho do array. Na verdade, o Quicksort utiliza espaço adicional devido à pilha de recursão: em média O(log n) e, no pior caso, O(n). O espaço não é proporcional ao tamanho total do array (O(n)), exceto no pior caso, e ainda assim é uma afirmação enganosa, pois a implementação clássica ordena in‑place com espaço extra apenas para a recursão.
Alternativa E — ❌ Incorreta
Afirma que o Quicksort sempre seleciona o primeiro elemento como pivô. A escolha do pivô pode variar: primeiro, último, elemento do meio, mediana de três, aleatório etc. O algoritmo não impõe que o pivô seja sempre o primeiro; isso é apenas uma das implementações possíveis.
NÃO CAIA NESSA!
A banca explora generalizações indevidas nas alternativas C e E com a palavra sempre. O Quicksort não é "sempre" mais lento que o Bubble Sort, nem "sempre" seleciona o primeiro elemento. Fique atento a termos absolutos que distorcem a realidade do algoritmo.
PEGA ESSA DICA!
Memorize as características centrais do Quicksort: divide‑and‑conquer, não estável, complexidade média O(n log n), pior caso O(n²) (ocorre com pivô desbalanceado), espaço O(log n) na média. Compare com outros algoritmos (Mergesort, Heapsort) para fixar as diferenças.
Gabarito: letra A — a única que descreve corretamente o funcionamento do Quicksort.