Questão de Algoritmos e Estrutura de Dados — Algoritmos — INSTITUTO AOCP 2019
Algoritmos e Estrutura de Dados›Algoritmos
Código
qq513960
Banca
INSTITUTO AOCP
Órgão
EMPREL
Ano
2019
Nível
Superior
Cargo
Analista de Sistemas
Assinale a alternativa correta acerca do algoritmo Quicksort.
AImplementa técnicas que possibilitam pressupor a sua entrada.
BÉ utilizada uma árvore binária para a sua implementação.
CNão ordena, apenas realiza buscas.
DÉ o mais rápido para a ordenação.
EBaseia-se no paradigma de dividir e conquistar.
Revelar gabarito e comentário▾
GabaritoE — Baseia-se no paradigma de dividir e conquistar.
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 e o paradigma Dividir e Conquistar
Gabarito: letra E. O algoritmo Quicksort é um dos mais conhecidos para ordenação e se baseia no princípio de dividir e conquistar: ele seleciona um pivô, particiona o array em duas sublistas (menores que o pivô e maiores que o pivô) e, recursivamente, ordena cada sublista. Essa é a definição clássica do método, conforme descrito em livros de algoritmos como Cormen et al. (Algoritmos: Teoria e Prática).
A banca testa o conhecimento fundamental sobre o Quicksort, mas também explora um distrator comum: a falsa ideia de que ele é "o mais rápido".
Quicksort
1Paradigma
Dividir e conquistar
2Funcionamento
Seleciona pivô
Particiona em sublistas
Menores que o pivô
Maiores que o pivô
Ordena recursivamente
3Complexidade
Média: O(n log n)
Pior caso: O(n²)
4Características
Ordenação (não busca)
Sem suposição sobre entrada
Sem árvore binária explícita
LEVEL · soulevel.com.br
Alternativa A — ❌ Incorreta
Afirma que o Quicksort "implementa técnicas que possibilitam pressupor a sua entrada". Isso não é verdade. O Quicksort não faz nenhuma suposição sobre os dados de entrada; ele trata qualquer sequência da mesma forma, executando as etapas de particionamento e recursão. A descrição genérica de "pressupor a entrada" não se aplica a este algoritmo específico.
Alternativa B — ❌ Incorreta
Diz que "é utilizada uma árvore binária para a sua implementação". O Quicksort não usa explicitamente uma árvore binária; sua implementação típica trabalha diretamente sobre o array, usando índices e recursão. Embora a recursão possa ser visualizada como uma árvore de chamadas, a estrutura de dados subjacente não é uma árvore binária. Outros algoritmos como HeapSort usam heap (árvore binária), mas o Quicksort não.
Alternativa C — ❌ Incorreta
Afirma que o Quicksort "não ordena, apenas realiza buscas". Isso é falso: o Quicksort é um algoritmo de ordenação, projetado para organizar elementos em uma sequência (crescente ou decrescente). Ele não realiza buscas.
Alternativa D — ❌ Incorreta
Afirma que o Quicksort "é o mais rápido para a ordenação". Isso é um exagero e uma generalização incorreta. O Quicksort tem complexidade média O(n log n), mas seu pior caso é O(n²). Algoritmos como MergeSort e HeapSort também têm complexidade O(n log n) em todos os casos e podem ser mais rápidos em cenários específicos. Portanto, não é correto afirmar que é "o mais rápido".
NÃO CAIA NESSA!
A alternativa D é o distrator clássico. Muitos associam o Quicksort à rapidez por causa do nome "Quick" e por ser amplamente utilizado, mas não se pode afirmar que ele é o mais rápido em termos absolutos — existem variações e outros algoritmos com desempenho similar ou superior dependendo do contexto. Fique atento a esse tipo de generalização absoluta ("sempre", "nunca", "o mais") em questões de algoritmos.
Alternativa E — ✅ Correta ⟵ GABARITO
"Baseia-se no paradigma de dividir e conquistar." Exato. O Quicksort é um exemplo paradigmático dessa técnica: ele divide o problema (o array) em subproblemas menores (partições) e resolve cada um recursivamente. Essa é a definição que consta em todos os materiais didáticos sobre algoritmos de ordenação.